백준 11057번 C++ 풀이

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

11057번: 오르막 수

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	실버 1

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

---

완전 탐색으로 풀고 싶어도, 10^1000만큼의 숫자를 저장할 자료형도 없고, 문자열로 처리한다고 해도, 경우의수가 너무 많기 때문에, 아무래도 dp문제라고 보는게 맞다고 판단했다.

일단, N = k인 오르막 수는, 생각해보면 N = k-1의 경우를 확장한 것과 다름이 없을 것이다. 무슨 뜻이냐면, k-1의 모든 경우도 오르막 수일 것이다. 이제 이 경우에서 제일 오른쪽에 숫자를 하나 더 쓰면, 그것이 N = k이 되고, 그런 경우에서 오르막수가 되는 모든 경우를 세면 되는 것이다. 이를 반복하면 N = k는 N = 1인 경우에서 점점 올라올 수 있겠다(당연한 귀납법).

 

그러면 오르막 수를 만들어 보자. 일단 1의 자리에 0이 오는 경우는 어떤 경우일까? 10의 자리가 0이어야 한다.

1이 오는 경우는? 10의 자리가 0또는 1이면 올 수 있다.

2가 오는 경우? 0~2가 오면 된다.

이를 일반화하면 음이 아닌 한자리 수의 정수 n이 1의 자리에 오려면, 10의 자리가 0 ~ n이어야 한다.

 

그러면 천천히 N = 1부터 올라가보자. N = 1이면 0 ~ 9의 범위일 것이고, 한자리 수는 그 자체로 정렬되어있다고 볼 수 있다. 그러니 N = 1이면 답은 10이다. 1의 자리에 0 ~ 9가 올 수 있는 경우의 수를 저장한 배열을 만들어보면, 다음과 같다.

 

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

 

본인들 자체가 1의 자리에 위치해있으니 당연하다. 그리고 각 경우의 수를 합하면 그것이 N = 1일때의 답 10이 된다.

 

N = 2를 보자. 0이 올 수 있는 경우는 무조건 10의 자리가 0이어야 한다(이 문제에서는 숫자가 0으로 시작할 수 있다.) 1과 2가 오는 경우는 앞서 말한 것처럼 각각 10의 자리에 0, 1인 경우와 0 ~ 2인 경우이다. 아까 일반화했듯이 n이 오려면 10의 자리가 0 ~ n이어야 하니까말이다. 이를 다르게 생각해보면 N = 2에서 1의 자리에 n이 올 수 있는 경우의 수는 N = 1일때의 0 ~ n이 오는 경우의 수의 총합이 된다는 것이다. 그러니 1이 오는 경우는 01, 11인 2, 2가 오는 경우는 3, 3이 오는 경우는 4....가 된다

.

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

 

마찬가지로 N = 3인 경우에서 0이 올 수 있는 경우의 수는 1이고 1이 오는 경우는 N = 2에서 0, 1이 오는 경우의 합인 3, 2가 오는 경우는 6....이 될 것이다.

 

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
1	2	3	4	5	6	7	8	9	10
1	3	6	10	15	21	28	36	45	55

 

위 배열을 dp배열이라고 하고 일반화를 해보면 누적합으로 생각할 수 있다. N = 2은 N = 1일때의 배열을 누적합으로 재구성한 것과 같고, N = 3은 N = 2를 누적합으로 재구성한 것이다. 그러니 N = k일때는 N = k-1배열의 누적합이 된다.

 

#include <bits/stdc++.h>
using namespace std;
#define MOD 10007

int sol(int n) {
    int dp[10];
    fill(dp, dp + 10, 1);

    for(int i = 1; i < n; i++) {
    // 기존 배열을 누적합으로 바꾼다.
    // 우리가 알고자 하는 것은 N = n일때의 배열의 전체 합이기 때문에
    // 중간 배열을 저장할 필요도 없고, 저장해둘 필요도 없다.
        for(int j = 0; j < 9; j++) {
            dp[j + 1] += dp[j] % MOD;
            dp[j + 1] %= MOD;
        }
    }
    return accumulate(dp, dp + 10, 0) % MOD;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    cout << sol(n);
}