[2688번] 줄어들지 않아

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

전형적인 DP 문제이다.

dp[i][j]의 의미는 다음과 같다.

왼쪽부터 i번째 수가 j일때 그때의 dp값이라고 정의한다.

예를들어 

dp[2][3]은 ㅁ3ㅁㅁ... 이라고 생각할 수 있다.

dp[5][7]은 ㅁㅁㅁㅁ7ㅁㅁ... 이라고 생각할 수 있다.

dp[1][i]는 모두 1이 된다. 왜냐면 첫번째 자리에서의 줄어들지 않는 수는 모두 1개이기 때문이다.

dp[1][0] 은 숫자 0이 차지할것이고

dp[1][1] 은 숫자 0이 차지할것이고

...

dp[1][9] 는 숫자 9가 차지할것이기 때문이다.

이제 dp를 구해보자.

이때 아래의 코드 처럼 dp[i][j] += dp[i-1][k]가 왜 성립하는지 알아보자.

dp[i][j]를 구하기 위해서는 이전의 i-1의 값들을 알아야한다.

이때 dp[i-1][~]에 대해 모든 값을 더하면 안되고, 줄어들지 않는 수에 대해서만 더해주어야 한다.

예를들어 dp[4][3]을 구하기 위해서는 dp[3][0] + dp[3][1] + dp[3][2] + dp[3][3]에 대해서만 해야한다.

즉, ㅁㅁㅁ3이 되기 위해서는

ㅁㅁ0

ㅁㅁ1

ㅁㅁ2

ㅁㅁ3 에 대한 dp값만 이용해야 한다는 의미이다. 

이 dp값만 이용해야 결국

ㅁㅁ03

ㅁㅁ13

ㅁㅁ23

ㅁㅁ33에 대한 값을 모두 알 수 있기 때문이다.

소스 코드 : 

#include <iostream>
#include <cstdio>

 
using namespace std;
 
typedef long long ll;
 
ll dp[65][11];
 
int main()
{
    for (int i = 0; i <= 9; i++)
        dp[1][i] = 1;
 
    for (int i = 2; i <= 64; i++)
        for (int j = 0; j <= 9; j++)
            for(int k = 0; k <= j; k++)
                dp[i][j] += dp[i - 1][k];
 
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        int n;
        scanf("%d", &n);
 
        ll ans = 0;
 
        for (int i = 0; i <= 9; i++)
            ans += dp[n][i];
 
        printf("%lld\n", ans);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>