[BOJ 11057] 오르막 수

문제 출저 : https://www.acmicpc.net/problem/11057

 

풀이 : 

 

DP문제입니다.

0~9까지의 숫자를 사용하여 각 자릿수가 주어질 때 오르막 수의 갯수를 찾는 문제입니다.

00 이나 11 같이 앞의 숫자가 같아도 오르막 수로 취급되니 주의해주고

데이터를 쌓을 때 (자기 자릿수 -1)일때 0부터 자기자신 까지 나온 오르막 수를 다 더합니다.

 

예를 들어 자릿수가 2이고 마지막 수가 2이라 하면 (cache[2][2])

자릿수가 1인 0,1,2로 오르막 수를 만들 수 있으니 자릿수가 2면서 마지막수가 2인 오르막수는 3개가 됩니다.

자릿수가 3이고 마지막 수가 2라고하면

0으로 끝나는 00로 1개, (cache[2][0])

1로 끝나는 01 11로 2개, (cache[2][1])

2로끝나는 02 12 22로 3개, (cache[2][2])

따라서 총 6개의 오르막 수를 만들 수 있게 됩니다.

#include<stdio.h>
 
int n,cache[1001][10],ret;
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < 10; i++)cache[1][i] = 1;
    for (int i = 2; i <= n;i++)
    {
        for (int j = 0; j < 10; j++)
        {
            for (int z = 0; z <= j; z++)cache[i][j] = (cache[i][j] + cache[i - 1][z])%10007;
            if (i == n)ret = (ret + cache[i][j])%10007;
        }
    }
    printf("%d", n==1 ? 10 : ret);
}