[BOJ / C++] 2688번 : 줄어들지 않아

문제

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다. 

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

출력

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

Solved.ac 레벨

실버 I

풀이

#include <bits/stdc++.h>

using namespace std;

int t;
long long dp[65][10];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    for(int i = 0; i <= 9; i++){
        dp[1][i] = 1;
    }

    for(int i = 1; i <= 64; i++){
        for(int j = 0; j <= 9; j++){
            for(int k = j; k <= 9; k++){
                dp[i][j] += dp[i - 1][k];
            }
        }
    }

    cin >> t;

    while(t--){
        int n;
        long long ans = 0;
        cin >> n;


        for(int i = 0; i <= 9; i++){
            ans += dp[n][i];
        }

        cout << ans << "\n";
    }


    
    return 0;
}

다이나믹 프로그래밍 (DP) 문제다.

 

long long 타입의 dp[65][10] 배열은 수의 길이와 0 ~ 9까지의 수로 끝나는 줄어들지 않는 수의 개수를 담기 위한 배열이다.

1자리 수는 모두 줄어들지 않는 수이므로 길이가 1이면서 0 ~ 9로 끝나는 줄어들지 않는 수의 개수를 1로 초기화시켜준다.

for(int i = 0; i <= 9; i++){
	dp[1][i] = 1;
}

문제는 여러 개의 테스트케이스에 대응해야 하므로 길이가 64인 줄어들지 않는 수들의 개수를 모두 구해놓기로 했다.

 

N = 2일 때를 예로 들어보자

dp[2][j]일때 j의 앞에 올 수 있는 수를 정리한 표이다. 맨 윗 행은 j의 범위다.

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0
	1	1	1	1	1	1	1	1	1
		2	2	2	2	2	2	2	2
			3	3	3	3	3	3	3
				4	4	4	4	4	4
					5	5	5	5	5
						6	6	6	6
							7	7	7
								8	9

수의 개수의 합, 즉 길이가 2인 줄어들지 않는 수의 개수는 55이다.

dp[2][2]의 경우를 보면 dp[1][0]~dp[1][2]까지의 합이다.

따라서 점화식으로 나타내면 다음과 같다.

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

답은 길이가 n일때 0~9의 합을 구하면 된다.

 

2688번: 줄어들지 않아