[BEAKJOON] 2688_줄어들지 않아_C언어_(11057 오르막수와 같음)

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

풀이

오랜만에 알고리즘을 다시 풀었다...최근에 피파에 빠져서......ㅜ,ㅠ

이건 예전에 풀었던 오르막수와 90%동일한 문제이다. 다이나믹 프로그래밍이며 이차원 배열을 통해서 풀어야된다.

이 문제에서 다음에 올 수는 맨 마지막에 있는 숫자보다 큰 수들이다. 따라서 맨 뒤의 숫자들에 따라 다음에 올 경우의 수들이 달라진다.

n=1일 경우

0일 경우 0과 같거나 큰 0~9의 숫자들이 올 수 있으므로 경우의 수가 10

1일 경우 1과 같거나 큰 1~9의 숫자들이 올 수 있으므로 경우의 수가 9

.

.

.

.

9일 경우 9와 같거나 큰 수는 9 하나이므로 9뒤에 올 수 있는 경우의 수는 1이다.

따라서 n은 1일 경우 총 경우의수가 55이다.

n=2일 경우는

0뒤에 올 수있는 수는 n=1일 때의 경우의 수 55이다.

1뒤에 올 수 있는 수는 n=1일 때 경우의 수에서 뒤의 수자가 0일 경우 10을 뺀 45이다.

.

.

.

9일 경우는 뒤에 무조건 9밖에 못 오므로 경우의 수는 1이다.

아래 표로 예시를 적어보았다. 여기서 n의 때의 토탈은 n+1에서 맨 뒤가 0일 때의 경우의 수가 된다.

맨 뒤의 수/n	n=1	n=2	n=3	n=4
0	10	55	220	715
1	9	45	165	495
2	8	36	120	330
3	7	28	84	210
4	6	21	56	126
5	5	15	35	70
6	4	10	20	35
7	3	6	10	15
8	2	3	4	5
9	1	1	1	1
총 경우의 수	55	220	715	2002

오르막 수와 다른점은...특정수로 나누어주냐 마냐의 차이 같다. int형으로 해주니까 틀렸다고 하여 범위를 벗어난 것 같아 unsinged long long형으로 처리하였다.

제출한 코드

#include <stdio.h>
unsigned long long arr[67][11] = { 0 };
 
unsigned long long total(int n)
{
    unsigned long long t = 0;
    for (int i = 0; i < 10; i++)
        t += arr[n][i];
    return t;
}
 
int main()
{
    int n = 2;
 
    for (int i = 10; i > 0; i--)
        arr[1][10 - i] = i;
 
    arr[1][10] = 55;
    arr[0][10] = 10;
 
    for (int i = 2; i < 65; i++)
    {
        arr[i][0] = arr[i - 1][10];
        for (int j = 1; j < 11; j++)
        {
            arr[i][j] = arr[i][j - 1] - arr[i - 1][j - 1];
        }
        arr[i][10] = total(i);
    }
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int num;
        scanf("%d",&num);
        printf("%llu\n", arr[num - 1][10]);
    }
 
    return 0;
}