백준 10844 쉬운 계단 수 Java

dp배열을 1차원 배열로만 만들어서 쓰다가

2차원 배열로 만들어 써야하는 첫 번째 문제였다.

애초에 2차원 배열로 접근해야 하는지도 생각해내지 못했다.

 

dp[길이 n][마지막 자리 수]로 접근해야 한다.

n이 1일 땐 {1, 2, 3, 4, 5, 6, 7, 8, 9} 한자리이기 때문에 쉬운 계단 수가 총 9개 이고

dp[1][i] = 1 일 것이다. 

n이 2일 땐 {12, 21, 23, 32, 34 ...} 일것이고 

dp[2][2] 일 때를 생각해보면  {12, 32} 

dp[2][2] = 2일 것이다.

쉬운 계단 수는 차이가 1이 나는 것만 가능하기 때문에

미리 구해둔 dp[n-1]에서 [마지막 자리수+1] 과 [마지막자리수-1]을 해준 값을

더해주면 되는 것이었다.

따라서 점화식은 dp[n] = dp[n-1][마지막 자리수-1] + dp[n-1][마지막 자리수+1]이다.

당연히 n번째 값을 구할 때는 n번째 배열의 0부터 9까지 모든 자리수를 더하면 된다.

 

주의할 점은 [마지막 자리수-1] 과 [마지막 자리수+1]을 하기 때문에

마지막자리수가 0인 경우엔 -1로 오류가 나고

9인 경우엔 10으로 오류가 난다.

이 두가지 경우는 따로 처리를 해줘야 한다.

 

또한 값이 점점 커지기 때문에 dp배열을 long으로 해줘야 하고

다른 문제와 마찬가지로 값을 구했을 때 마다 문제에서 제시하는대로 나머지 연산을 해줘야한다.

 

이렇게 해서 제출했는데 또 틀렸다.

이유는 나머지 연산을 해주면서 값을 계속 저장 했음에도

답을 구하기위해 n번째 모든 자리수를 더하고 나서

다시 나머지 연산을 안해줬기 때문이다.

n을 최대값으로 하면 주어진 mod값을 넘어가는 걸 볼 수 있다.

 

public static void main(String[] args) {
        final int mod = 1000000000;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long [][] dp = new long[n+1][10];
        
        for(int i=1; i<10; i++)
            dp[1][i] = 1;
        
        for(int i=2; i<=n; i++) {
            for(int j=0; j<10; j++) {
                if(j == 0)
                    dp[i][j] = dp[i-1][j+1];
                else if(j == 9)
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
                dp[i][j] %= mod;
            }
        }
        long answer = 0;
        for(int i=0; i<10; i++)
            answer += dp[n][i];
        
        System.out.println(answer%mod);
    }

 

다른 사람들의 블로그에서 알고리즘 풀이 글들을 보면서

왜이렇게 이해하기 힘들게 적어놨을까..하고 불평불만을 많이 했었는데

그분들은 설명을 잘하는 것이었다.

글로 설명하기가 참 어렵다는 걸 깨달았다.