Table of contents

백준 쉬운 계단 수

45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

N이 주어졌을 때, 길이가 N인 숫자에서 모든 자리수의 차이가 1인 수를 계단 수라고 한다. 이런 계단 수의 갯수를 구하는 문제이다.

첫번째 풀이

@Test
public void test() {
    assertThat(solution(1))
            .isEqualTo(9);
    assertThat(solution(2))
            .isEqualTo(17);
    assertThat(solution(3))
            .isEqualTo(32);
}

// 오답, n = 3까지만 맞음
private static int failSolution(int N) {
    long[] dp = new long[101];
    dp[1] = 9;

    for (int i = 2; i <= N; i++) {
        dp[i] = ((dp[i - 1] * 2) - (i - 1)) % 1_000_000_000;
    }

    return (int) dp[N];
}
  • 1 -> 10, 12 -> 101, 121, 123
  • 2 -> 21, 23 -> 210, 212, 232, 234
  • 3 -> 32, 34 -> 321, 324, 343, 346
  • 4 -> 43, 45 -> 432, 434, 454, 456
  • 5 -> 54, 56 -> 543, 545, 565, 567
  • 6 -> 65, 67 -> 654, 656, 676, 678
  • 7 -> 76, 78 -> 765, 767, 787, 789
  • 8 -> 87, 89 -> 876, 878, 898

처음에는 N이 3인 경우의 수 까지만 생각하고 dp[i] = (dp[i - 1] * 2) - (i - 1) 라는 점화식을 세웠다. 그러나, N이 3을 넘어가면 잘못된 결과를 계산한다.

두번째 풀이

@Test
public void test() {
    assertThat(solution(1))
        .isEqualTo(9);
    assertThat(solution(2))
        .isEqualTo(17);
    assertThat(solution(3))
        .isEqualTo(32);
    assertThat(solution(100))
        .isEqualTo(18404112);
}


public static int solution(int N) {
    long[][] dp = new long[101][11];

    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]) % 1_000_000_000;
        }
    }

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

    return (int) (sum % 1_000_000_000);
}
  • 1 -> 10, 12 -> 101, 121, 123
  • 2 -> 21, 23 -> 210, 212, 232, 234
  • 3 -> 32, 34 -> 321, 324, 343, 346
  • 4 -> 43, 45 -> 432, 434, 454, 456
  • 5 -> 54, 56 -> 543, 545, 565, 567
  • 6 -> 65, 67 -> 654, 656, 676, 678
  • 7 -> 76, 78 -> 765, 767, 787, 789
  • 8 -> 87, 89 -> 876, 878, 898

규칙을 찾다보면 다음과 같은 규칙을 발견할 수 있다. N은 자릿 수, L은 끝 자리가 L인 계단 수의 갯수를 의미한다.

  • 점화식 1. 끝 자리가 0인 경우 1 (+1)만 추가
    • dp[N][L] = dp[N - 1][L + 1]
  • 점화식 2. 끝 자리가 0보다 크고 9보다 작은 경우 끝 자리에 이전 끝자리 수 +- 1를 추가
    • dp[N][L] = dp[N - 1][L - 1] + dp[N - 1][L + 1]
  • 점화식 3. 끝 자리가 9인 경우 8 (-1)만 추가
    • dp[N][L] = dp[N - 1][L - 1]
for (int i = 2; i <= N; i++) {
        dp[i][0] = dp[i - 1][1];

위 코드가 점화식 1에 해당한다.

for (int j = 1; j <= 9; j++) {
    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1_000_000_000;
}

위 코드는 점화식 2번과 3번에 해당한다. 점화식 3번, 끝 자리가 9인 경우를 처리하지 않는 이유는 dp[i][10]의 값은 항상 0이라 굳이 처리할 필요가 없기 때문이다.