[백준 11057] 오르막 수

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

1. 문제 이해

수의 자리가 오름차순을 이루는 수를의 개수를 구하는 문제이다.

1234와 같은 수. 2232 아님.

수의 길이 N이 주어졌을 때, 길이가 N인 오르막수의 개수를 10,007로 나눈 나머지를 출력함

 

2. 조건

0으로 시작할 수 있다.

 

3. 풀이

dp는 오르막 수를 가지고 있는 2차원 배열로 잡았다.

어떤 규칙을 가지고 있을지 찾아보다가 아래와 같이 등차수열의 합이 반복됨을 알았다.

등차수열의 합 Sn = n(a1 + an)/2 

하지만 이는 1의 자리가 9일 때의 for문과

자릿수가 바뀔 때마다 -1되는 수를 알아내야하고 또 이 합을 구해야하기 때문에

시간 초과가 예상 됐다 ...

분명 수가 어떤식으로 반복되는 것은 분명한데 뭐가 있을 까 하다가

루미큐브처럼 생각이 들었다 

맨 마지막 수 9이면 2자리에서 10개, 8이면 9개, ... 이런 식으로 반복되더라 !

길이(n), 맨 끝의 수(i)에 따른 오르막 수의 개수를 저장해야 했다.

그래서 dp[n][i]로 잡고 n과 i의 수를 그래프로 정리해봤다.

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

dp[i][j] = dp[i-1][j]+dp[i][j-1] 드디어 찾았다 ...

식으로 가보자고 ~

#include <iostream>
using namespace std;

int dp[1001][10];

int main() {
    int n, result = 0;;

    cin >> n;

    for (int i = 0; i < 10; i++) { //길이, 끝나는 숫자
        dp[1][i] = 1;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0) {
                dp[i][j] = 1;
                continue;
            }
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 10007;
        }
    }

    for (int i = 0; i < 10; i++) {
        result += dp[n][i];
    }

    cout << result % 10007;

    return 0;
}

 

4. 구현/디버깅

dp[i][j] 에 값을 넣을 때 10007를 해주지 않아서 '틀렸습니다'가 떴다.

혹시나 하고 넣었는데 아마 int 범위 밖의 수가 더해져서 그랬던 것 같다.