[C언어] 백준 | 11057번 오르막 수

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

11057번: 오르막 수

안녕하세요. 황지원입니다.

dp를 그제 처음 배워가지고 dp문제를 중점으로 한동안 풀어볼 생각입니다.

서울대학교, 부산대학교 분에게 백준 문제를 풀 거라면 c++을 하라고 추천받았습니다. 실버 3에서 실력이 멈춘 것 같았는데, 알고 보니 문제를 풀려면 언어 공부가 아닌 알고리즘 공부를 해야 하더라고요. dp 공부하고 바로 실버 1문제를 풀 수 있게 되었습니다. 물론 운이 따라줬지만요.
아무튼 c++을 추천받았습니다만, 제가 현재 c언어 수업을 듣고 있거든요.
둘이 아예 다른 언어이면 상관이 없습니다. 하지만 비슷한 언어라서 제가 헷갈릴까봐 걱정이 되어 둘이 같이는 못 배울 듯합니다.

아무튼 그래서 정렬 등과는 다르게 c언어로 아주 쉽게 구현이 가능한 다이나믹 프로그래밍 문제를 풀 생각입니다.
근데 피보나치 문제와는 다르게 제가 오늘 푼 것도 dp의 범주에 들어가는지는 모르겠네요.
사족이 길었네요.

시작하겠습니다.

---

1을 입력받았을 때를 생각해보면
0 1 2 3 4 5 6 7 8 9
모두 오르막 수임을 알 수 있습니다.

맞죠?

2를 입력받아서 이제 0~9의 뒤에 숫자를 하나씩 덧붙여 오르막 수를 만든다고 가정을 해봅시다.
9의 뒤에는 1개의 수만 올 수 있습니다. 9이죠.
8의 뒤에는 2개의 수가 올 수 있습니다. 8, 9 입니다.
7의 뒤에는 3개
6의 뒤에는 4개
.
.
.
0의 뒤에는 10개의 수가 올 수 있습니다. (0부터 9까지 모두 가능하니까요.)

제가 여기까지만 하고 어떻게 풀어야하나 고민을 했는데요, 여기에 규칙이 있습니다.

2를 입력받아서 만들어진 오름 수를 보면,
0으로 끝나는 수는 1개뿐입니다. 00이죠.
1로 끝나는 수는 2개입니다. 01과 11이죠.
2로 끝나는 수는 3개입니다. 02, 12, 22.
3으로 끝나는 수는 4개입니다.
.
.
9로 끝나는 수는 10개입니다. 09, 19, 29, 39, 49, 59, 69, 79, 89, 99

3을 입력받아서 위에서 만들어진 오름수의 뒤에 숫자를 덧붙여봅시다.

0으로 끝나는 수는 또 1개뿐이겠죠? 000
1로 끝나는 수는 3개입니다. 001, 011, 111
2로 끝나는 수는 6개입니다. 002, 012, 112, 022, 122, 222

규칙성을 찾으셨나요?

일단 0으로 끝나는 수는 1개밖에 만들어질 수 없습니다.
그리고 3번째에서
1로 끝나는 수는 2번째에서 기존에 1로 끝나는 수 01, 11과 1보다 작은 숫자인 0으로 끝났던 00을 더해 3개입니다.
2로 끝나는 수는 2번째에서 기존에 2로 끝났던 02, 12, 22와 00, 01, 11가 2로 끝날 수 있으니 6개이죠.
3으로 끝나는 수는 4 + 3 + 2 + 1로 10입니다.
4로 끝나는 수는 5 + 4 + 3 + 2 + 1로 15
.
.
.
9로 끝나는 수는 10 + 9 + .. + 1 로 55개입니다.
제가 한 말을 이해하셨다면
arr[0] = 1;
arr[i] = arr[i - 1] + arr[i];
이 부분을 이해하실 겁니다.

추가적으로 미리미리 10007로 나눠놔야 정수 오버플로우가 생기지 않겠죠?
이걸 푸시는 분들이라면 다 알고 계실 거라고 생각합니다.

제 첫 실버 1 문제였습니다.
블로그 만든 지 얼마나 됐다고 검색해서 들어오는 분들이 계셔서 열심히 적어봤습니다.
문제 푸는데 8분, 블로그에 적는데 30분 걸렸습니다.

감사합니다.

#include <stdio.h>

int main(void) {
    long long arr[11] = {1,2,3,4,5,6,7,8,9,10};
    int n;
    int m = 0;
    scanf("%d", &n);
    if(n == 1) {
        printf("10");
        return 0;
    }
    for(int j = 0; j < n - 2; j++) {
    for(int i = 1; i < 10; i++) {
        arr[0] = 1;
        arr[i] = (arr[i - 1] + arr[i]) % 10007;
    }
    }
    for(int i = 0; i < 10; i++) {
        m += arr[i];
    }
    m %= 10007;
    printf("%d", m);
    return 0;
}