Table of contents

백준 오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

N이 주어졌을 때, 길이가 N인 수의 자리가 오른차순을 이루는 수를 오르막 수라고 한다. 이런 오르막 수의 갯수를 구하는 문제이다.

첫번째 풀이

@Test
public void test() {
    assertThat(solution(1))
        .isEqualTo(10);
    assertThat(solution(2))
        .isEqualTo(55);
    assertThat(solution(3))
        .isEqualTo(220);
}

private static int solution(int n) {
    long[][] dp = new long[1001][10];
    for (int i = 0; i < 10; i++) {
        dp[1][i] = 1;
    }

    for (int N = 2; N <= n; N++) {
        dp[N][9] = 1;
        for (int L = 0; L <= 9; L++) {
            for (int M = L; M <= 9; M++) {
                dp[N][L] += dp[N - 1][M];
            }
            dp[N][L] %= 10_007;
        }
    }

    int sum = 0;
    for (int i = 0; i < 10; i++) {
        sum += dp[n][i];
    }
    return sum % 10_007;
}

N이 3일 때 까지만 분석해보자.

N = 1, 9개

  • 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

N = 2, 55개

  • 00, 01, 02, 03, 04, 05, 06, 07, 08, 09
    • 10개
  • 11, 12, 13, 14, 15, 16, 17, 18, 19
    • 9개
  • 22, 23, 24, 25, 26, 27, 28, 29
    • 8개
  • 33, 34, 35, 36, 37, 38, 39
    • 7개
  • 44, 45, 46, 47, 48, 49
    • 6개
  • 55, 56, 57, 58, 59
    • 5개
  • 66, 67, 68, 69
    • 4개
  • 77, 78, 79
    • 3개
  • 88, 89
    • 2개
  • 99
    • 1개

N = 3, 첫번 째 00 ~ 99에서만 55개 sum(1..10)

  • 000, 001, 002, 003, 004, 005, 006, 007, 008, 009
  • 011, 012, 013, 014, 015, 016, 017, 018, 019
  • 022, 023, 024, 025, 026, 027, 028, 029
  • 033, 034, 035, 036, 037, 038, 039
  • 044, 045, 046, 047, 048, 049
  • 055, 056, 057, 058, 059
  • 066, 067, 068, 069
  • 077, 078, 079
  • 088, 089
  • 099

N은 자릿 수, L은 L번째 계단을 의미한다.

  • N = 3, L = 0인 000 ~ 099
    • N = 2의 결과와 갯수가 같다
  • N = 3, L = 1인 111 ~ 199
    • N = 2의 결과에서 맨 윗칸을 떼어난 것의 갯수와 같다.

N = 1 -> dp[N][L] = 1

N > 1 -> dp[N][L] = dp[N - 1][L] +

​ (dp[N - 1][L + 1] + dp[N - 1][L + 2] + ...... dp[N - 1][L + M]) (M <= 9 까지)

두번째 풀이

@Test
public void test2() {
    assertThat(solution2(1))
        .isEqualTo(10);
    assertThat(solution2(2))
        .isEqualTo(55);
    assertThat(solution2(3))
        .isEqualTo(220);
}

private static int solution2(int n) {
    long[][] dp = new long[1001][10];
    for (int i = 0; i < 10; i++) {
        dp[1][i] = 1;
    }

    for (int N = 2; N <= n; N++) {
        dp[N][9] = 1;
        for (int L = 8; L >= 0; L--) {
            dp[N][L] = dp[N - 1][L] + dp[N][L + 1];
            dp[N][L] %= 10007;
        }
    }

    int sum = 0;
    for (int i = 0; i < 10; i++) {
        sum += dp[n][i];
    }
    return sum % 10_007;
}

첫번째 풀이와 비교해보자. dp[N][L + 1]은 dp[N][L]에서 맨 윗 층(9개)을 떼어낸 것으로 볼 수 있다.

N = 4, L = 1

  • 111, 112, 113, 114, 115, 116, 117, 118, 119 <- dp[4][2]는 이 부분(9개)을 떼어낸 모습
  • 122, 123, 124, 125, 126, 127, 128, 129
  • 133, 134, 135, 136, 137, 138, 139
  • 144, 145, 146, 147, 148, 149
  • 155, 156, 157, 158, 159
  • 166, 167, 168, 169
  • 177, 178, 179
  • 188, 189
  • 199

N = 4, L = 2

  • 222, 223, 224, 225, 226, 227, 228, 229
  • 233, 234, 235, 236, 237, 238, 239
  • 244, 245, 246, 247, 248, 249
  • 255, 256, 257, 258, 259
  • 266, 267, 268, 269
  • 277, 278, 279
  • 288, 289
  • 299

점화식은 다음과 같다.

N = 1, dp[N][1~9] = 1

N > 1 && L == 9, dp[N][L] = 1

N > 1 && L <= 8, dp[N][L] = dp[N][L + 1] + dp[N - 1][L]

  • dp[N - 1][L]
    • 맨 위에 이어붙어야 할 층이다. ( N = 4, L = 1에서 굵게 표시된 맨 윗층이라고 볼 수 있음)
  • dp[N][L+1]
    • 현재 층의 아래 층부터 맨 마지막 층까지 형성된 계단 모양이다.
  • 아래 층부터 맨 마지막 층까지 형성된 계단 모양에 굵게 표시된 층을 이어붙이면 dp[N][L]이 완성된다.