[C++] 백준 - 11057 : 오르막 수

문제 링크

11057번: 오르막 수

 

풀이 ) DP

  각 숫자는 0부터 9의 숫자로 끝날 수 있다.

  또 m으로 끝나는 n자리 숫자는  m이하의 0 ~ m의 숫자로 끝나는 n-1자리 숫자 + m의 구조로 이루어져 있다.

  따라서 점화식은 memo[n][m] = ∑memo[n-1][i] (i = 0~m)이다.

  이 때 ∑memo[n-1][i] (i = 0~m-1) = memo[n][m-1]이므로 식을 다시 정리하면 다음과 같다.

  memo[n][m] = memo[n][m-1] + memo[n-1][m]

 

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1002][10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

int main(void)
{
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 1; i < n; ++i){
        memo[i][0] = memo[i-1][0];
        for(int j = 1; j < 10; ++j)
            memo[i][j] = (memo[i-1][j] + memo[i][j-1]) % 10007;
    }
    for(int i = 0; i < 10; ++i)
        ans += memo[n-1][i];
    printf("%d\n", ans % 10007);
    return 0;
}

 

주의점)

  - for문 내에서 모듈러 연산을 해주어 정수 오버플로우가 발생하지 않도록 한다.

  - memo[i][0]은 안쪽 for문에서 빼주어 런타임 에러를 방지한다.