[code.plus 알고리즘 기초] no. 10844

https://www.acmicpc.net/problem/10844

잘못된 방법

올바른 방법

package n10844;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] dp = new long[n+1][10];
 
        for(int i = 1; i<=9; i++){ // n이 1일때 마지막 숫자(i)가 나올 경우의 수 n이 1이기 때문에 당연히 전부 1이다.
            dp[1][i] = 1;
        }
 
        for(int i = 2; i < n+1; i++){
            for(int j = 0; j <= 9; j++){ // j는 마지막 숫자를 나타냄
                if(j >= 1){ // 1보다 크면
                    dp[i][j] += dp[i-1][j-1]; //마지막숫자(j) 보다 1작은 숫자의 경우의 수를 더해주고
                }
                if(j <= 8){ // 8보다 작으면
                    dp[i][j] += dp[i-1][j+1]; //마지막숫자(j) 보다 1큰 숫자의 경우의 수를 더해주고
                }
                dp[i][j] = dp[i][j] % 1000000000; // 마지막 dp[]의 결과에는 10억을 나눠주고 나머지값을 저장한다.
            }
        }
 
        long result = 0;
        for (int i=0; i<=9; i++) {
            result += dp[n][i];
        }
        result %= 1000000000;
 
        System.out.println(result);
    }
}