[알고리즘] 백준 10844 쉬운 계단 수 -dp-

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

10844번: 쉬운 계단 수

 

 

 백준 1463 1로 만들기 문제에 이어 동적계획법 다음단계인 쉬운계단수를 풀어봤습니다.

이전 문제보다 바로 2차원 배열로 접근해서 쉽게 풀수 있었습니다.

그리고 주의해야할점이 문제에 나와있는것처럼 %1000000000 을 해줘야합니다.

 

위와 같이 먼저 dp 정의를 세우고 dp[자릿수][오는숫자] = 경우의수;

dp 문제의 경우 대부분 초기 값을 몇개 세팅해주고 풉니다. 

위 그림은 두자리(N=2) 의 예시인데

앞자리는 0이 못오고 1~9가 올 수 있음을 알 수 있습니다.  그러므로 초깃값을 0빼고 다음과 같이 해줍니다.

for (int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }

 

그리고 다음 자리의 숫자의 경우의 수는 앞자리의 영향을 받는데 숫자가 9나 0은 앞자리 숫자와 1의 차이가 나는 경우 한가지 경우의 수밖에 없고 나머진 2가지 경우가 있습니다. 이 점을 사용하여 동적계획법을 풀이합니다. 이를 다음과 같이 처리합니다.

for (int i = 2; i <= N; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 9) {
                    dp[i][j] = dp[i - 1][j - 1] % 1000000000;
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j + 1] % 1000000000;
                } else {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
                }
            }
        }

 

그럼 마지막에 자릿수에 모든 경우의 수가 모여있을텐데 그것들을 다 더해준게 정답이 됩니다.

long answer = 0;
        for (int i = 0; i < 10; i++) {
            answer += dp[N][i];
        }

 

 

 

전체 코드는 다음과 같습니다.

import java.util.Scanner;

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

 

확실히 쓰면서 풀면 더 접근이 쉬워지는 것 같습니다.