[백준 2688번] 줄어들지 않아 (C++)

문제링크 : https://www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N;
ll dp[65][10]; //자릿수, 0~9

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> T;

    for(int i=0; i<=9; i++)
    {
        dp[1][i] = 1; //초기값 (한자릿수 0~9)
    }

    for(int i=2; i<=64; i++) //자릿수
    {
        for(int j=0; j<=9; j++) // 숫자 0~9
        {
            for(int k=j; k<=9; k++)
            {
                dp[i][j] += dp[i-1][k];
            }
        }
    }

    while(T--)
    {
        cin >> N;
        ll result = 0;
        for(int i=0; i<=9; i++) result += dp[N][i]; //N자릿수
        cout << result << "\n";
    }

    return 0;
}

 

1자릿수의 경우 올 수 있는 값이 각 0~9까지이다.

이를 이용해서 dp식을 초기화하고 시작한다.

dp는 [자릿수][오는 숫자]로 선언해주고 한자릿수의 경우 1이고, 각 값 0~9까지를 1로 초기화해준다. (dp[1][0~9]=1)

 

이제 3중 반복문을 사용하는데 각 인덱스는 자릿수, 숫자 0~9, 현 숫자 이후 ~ 9이다.

1을 초기화 해주었으므로 2부터 시작하며 현 dp[i][j] (자릿수, 현 숫자) 에 직전 자릿수의 값을 더해주게 된다.

숫자는 현 숫자보다 크거나 같아야 하므로 k=j부터 시작하게 되며, 직전 자릿수에 저장된 값들을 이용하여 더해준다.

(dp[i][j] += dp[i-1][k])

 

이러면 dp에 대한 계산을 미리 전부 해준 것이기 때문에 매테스트케이스마다 현재 입력받은 자릿수 N에 따른 합을 구해 매번 출력해주면 된다.

이때 주의해야할 것이 하나 있는데 계속에서 더해줌에따라 int 범위를 초과하는 케이스가 생기므로 dp식과 합을 저장할 result 변수를 longlong으로 선언해주어야 한다.