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

문제

https://www.acmicpc.net/problem/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자리 수의 개수를 출력한다.

---

Algorithm

가장 오른쪽 끝번째 자리부터 첫번째 자리순서대로 다음 자리의 숫자가 현재 자리보다 작거나 같은 모든 경우의 수를  탐색하는 백트래킹 방식의 구조에서 이미 한번 다녀온 값에 대한 중복되는 경우를 탐색시 마다 dp배열에 저장하여 중복을 피하는 방법으로 top-down dp 방식으로 문제를 해결하였다.

 

---

 

 

Code

#include<iostream>
using namespace std;
typedef long long LL;

LL dp[10][65]={0};
LL cnt_DP(int s,int n);
int main(){
    int t;
    int n;

    cin>>t;
    for(int i=0;i<t;i++){
        cin>>n;
        LL ans=0;
        for(int j=0;j<10;j++){//가장 오른쪽 자리 숫자 0~9 
            ans+=cnt_DP(j,n);
        }
        cout<<ans<<endl;
    }
}

LL cnt_DP(int s,int n){
    if(n==1){//가장 첫번째 자리에 도달한경우 cnt+1 
        return 1;
    }
    if(dp[s][n]){//중복되는 경우 저장된 값을 반환
        return dp[s][n];
    }

    for(int i=s;i<10;i++){//만약 없는경우 재귀 호출을 통한 다음 차례 탐색
        dp[s][n]+=cnt_DP(i,n-1);// 탐색 이후 값저장
    }
    return dp[s][n];// 값 반환
}