백준 10844번 쉬운 계단 수 :: 마이구미

이 글은 백준 알고리즘 문제 10844번 "쉬운 계단 수" 를 풀이한다.

풀이 방법으로는 동적계획법으로 설명한다.

문제 링크 - https://www.acmicpc.net/problem/10844

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

인접한 모든 자리수의 차이가 1인 수를 어떻게 찾을까?

직접 적어보면 쉽게 점화식을 만들어낼 수 있다.

N = 1
=> 1, 2, 3, 4, 5, 6 ......
N = 2
=> 10, 12, 21, 23, 32, 34, 43, 45 ......

N = 1 일 경우 0은 계단 수가 아니라는 것은 문제에서 명시했기 때문에, 실수하면 안된다.

N = 1, 2 일 경우, 비교해보면 결국 N은 N - 1일 때 수에서 +-1 을 1의 자리에 붙는다는 것을 알 수 있다.

그러한 규칙으로 점화식은 다음과 같이 만들 수 있다.

dp[N][L] = dp[N - 1][L - 1] + dp[N - 1][L + 1]
=> 길이가 N 일 때, 마지막 수가 L일 경우의 계단 수

주의할 점은 위의 점화식은 L이 (1 ~ 8) 일 때 성립한다.

왜냐하면 0은 +1을 한 1만 허용되고 9는 -1을 한 8만 적용되기 때문이다.

구체적인 점화식은 다음과 같다.

L =    0    => dp[N][L] = dp[N - 1][L + 1]
L = (1 ~ 8) => dp[N][L] = dp[N - 1][L - 1] + dp[N - 1][L + 1]
L =    9    => dp[N][L] = dp[N - 1][L - 1]

각 점화식을 조건에 따라 분기처리를 하면된다.

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];					
}

위처럼 나온다면 조금 더 생각해보면 좋다.

조금 더 생각하면 위 코드를 줄일 수도 있으니.... 최종 코드는 아래를 참고하자.

Github - https://github.com/hotehrud/acmicpc/tree/master/dp

카테고리 - 동적계획법 관련 문제

private void solve() {
    int n = sc.nextInt();
    long[][] dp = new long[101][11];
 
    // dp[N][L] = dp[N - 1][L - 1] + dp[N - 1][L + 1]
    // 길이 N, 마지막 숫자가 L일 경우
 
    for (int i = 1; i <= 9; i++) {
        dp[1][i] = 1;
    }
 
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][1];
        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 = 0; i < 10; i++) {
        sum += dp[n][i];
    }
    System.out.println(sum % 1000000000);
}