백준10844 쉬운 계단 수

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

10844번: 쉬운 계단 수

드디어 혼자 힘으로 동적계획법 문제를 풀었다. 처음에는 고민을 해도 문제가 풀리지 않았는데 3학년1학기때 보았던 동적계획법 강의를 조금 보고 Bottom-Up 개념을 다시 확실히하고 문제를 보니 어떤 방식으로 풀어야 할 지 생각이 났다. 먼저 2차원 배열을 통해 문제를 풀어야했는데 행의 크기는 0부터 9까지 10개의 자리를 할당해도 되지만 배열 인덱스오류를 방지하기위해 12개 자리를 할당했다. 

열의 크기는 N+1만큼 자리를 주었다. 이 문제를 해결할 때 사용되는 일반적인 경우는 현재 값보다 한 자릿 수가 큰 부분과 1차이가 났을 때 저장했던 값들을 더해주면 해결되었다. 식으로 작성하면

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

하지만 나온결과를 1,000,000,000 으로 나눈 나머지로 구해야 하므로 계산을 할때마다 이 수로 나눈 나머지를 저장했다.

 

 

풀이

 

package 동적계획법;
 
import java.io.*;
 
public class 쉬운계단수 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
         int  flag = 1000000000;
        long[][] dp = new long[12][N+1];
        dp[0][1] = 0;
 
        for(int i=2;i<=10;i++) //n이 1 인 경우
            dp[i][1] = 1;
 
 
        for(int i=2;i<=N;i++){
            for(int j=1;j<=10;j++){ //0부터 9까지 j-1==-1,j+1==9 경우방지를 위해 12자리로 만듬
                dp[j][i] = dp[j-1][i-1]%flag +dp[j+1][i-1]%flag;
                dp[j][i] %=flag;
 
            }
        }
        long res = 0;
        for(int j=1;j<=10;j++){
            res += dp[j][N];
            res%=flag;
        }
        System.out.println(res);
    }
}