백준 10844 - 쉬운 계단 수 [DP/JAVA]

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

 

---

dp 문제이므로 메모이제이션을 활용해야하니 이 점에 집중해보면 은근히 쉬운 문제다. 

dp[i][j] 2차원 배열을 만들었다. 여기서 

i : n 즉, 구해야하는 자리수

j : 구한 계단의 첫번째 수 

ex) n이 3일 때, 321 은 dp[3][3]의 방법 중 하나이다. 

 

점화식만 구하면 쉽다. dp[2][5]를 구한다고 할 때, 두자릿수이면서 5로 시작하는 수이므로 54, 56이 있다. 첫번째 수 5 뒤에 한자릿수 4,6을 붙이는 경우이므로 dp[2][5] = dp[1][4] + dp[1][6] 이다. 

한 가지 예시를 더 들자면 세자릿수이면서 5로 시작하는 수는 543, 545, 565, 567 총 4가지가 있다. 첫번째는 수 5 뒤에 두자릿수 43, 45, 65, 67 을 붙이는 경우이므로 dp[3][5] = dp[2][4] + dp[2][6] 이다. 

 

위 두 식을 통해서 

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 임을 알 수 있다. 

즉, n자릿수 중 j로 끝나는 수는 n-1자릿수 중 j-1, j+1로 끝나는 수의 합인 것이다. 

 

다만 예외가 있다.

1) 문제에서 0으로 시작할 수 없다고 했다. 따라서

dp[i][0] = dp[i-1][1] 

(실질적으론 dp[i][0]은 0으로 시작하는 수가 계단수가 아니라고 했으므로 0이겠지만 dp[i][0] = 0 으로 해놓으면 dp[i+1][1]값을 구할 때 문제가 생기기에 값은 유지하고 마지막에 계단수를 구할 때는 더해주지 않는다.) 

 

2) j=9일 때, j+1은 10이므로 없다. 따라서 

dp[i][9] = dp[i][8]

 

정리하면 

1) j=0일때, 

dp[i][0] = dp[i-1][1] 

 

2) j=9일때, 

dp[i][9] = dp[i][8]

 

3) j=1~8일때,

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

 

추가로 문제에서 1,000,000,000으로 나누어 주라고 했으므로 for 문에서 계속 나눠주면서 계산해야 한다. (마지막에 나누지 않고 중간에 나눠줘야 값이 넘치지 않으며, 중간중간 나눠줘도 결과값에 변화는 없다.) 

또한, int로 해보니 범위를 넘어선다는 오류가 떠서 dp와 sum을 long으로 설정했다. 

---

결론

1) j=0일때,

dp[i][0] = dp[i-1][1] 

2) j=9일때, 

dp[i][9] = dp[i][8]

3) j=1~8일때,

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

 

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 [101][10];
        
        for(int j=0; j<=9; j++){
            dp[1][j] = 1;
        }
        
        for(int i=2; i<=n; i++){
            dp[i][0] = dp[i-1][1];
            dp[i][9] = dp[i-1][8];
            
            for(int j=1; j<9; j++){
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
            }
        }
        
        long sum = 0;
        for(int i=1; i<=9; i++){
            sum = (sum + dp[n][i]) % 1000000000;
        }
        
        System.out.println(sum%1000000000);
    }
}