11057 오르막수

스터디 8주차

memo[i][j] : i번째 자릿수(숫자의 맨뒤부터)가 j일 때 가능한 오르막수의 개수

3중 포문으로 2번째 자릿수부터 n번째 자릿수까지, memo[i][0]부터 memo[i][9]를 구한다.

memo[i][j]는 i-1번째 자릿수에 대해 j부터 9까지를 구한 것임 (011, 012 ....... 019처럼)

최종답안은 memo[n][0]부터 memo[n][9]까지의 합이 됨

오답노트 :

계산 도중에 int의 범위를 벗어나기 때문에

포문을 돌릴 때도 10007로 나눠줘야 함

/*
오답노트:
포문에서도 10007로 나눠줘야함
계산 중에 int범위를 초과하게 되므로
https://www.acmicpc.net/board/view/16423
*/
#include <iostream>
#include <string.h>
#define SIZE 1001
using namespace std;
int n;
// memo[i][j] : i번째 자릿수(숫자의 맨뒤부터)가 j인 경우의 오르막수개수
int memo[SIZE][10];
 
 
 
int main() {
    cin >> n;
 
    // 한자리수의 경우엔 1가지만들 수 있음
    for (int i = 0; i <= 9; i++)
        memo[1][i] = 1;
 
    // 2번째 자리수부터 n번째 자리수까지
    for (int i = 2; i <= n; i++) {
        // memo[i][0]부터 memo[i][9]까지
        for (int j = 0; j <= 9; j++) {
            // 그 다음 자릿수가 j와 같은 수부터 9까지 (011, 012 ...)
            for (int k = j; k <= 9; k++) {
                memo[i][j] += memo[i - 1][k];
                memo[i][j] %= 10007;
            }
        }
    }
    
    // memo[n][0]부터 memo[n][9]까지의 합이 답
    int ans = 0;
    for (int i = 0; i <= 9; i++) {
        ans += memo[n][i];
    }
    cout << ans % 10007 << endl;
    
    return 0;
}