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

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

2688번: 줄어들지 않아

 

전형적인 dp문제입니다. 이전단의 결과값들이 현재 결과값에 영향을 미치기 때문입니다. 

예를 들어 n = 1일때 0 1 2 3 ~~ 9 로 총 10가지 경우의 수입니다.

 

n=2 일때  

0으로 시작할때  0~9 로 10개

1로 시작할때 1~9로 9개

2로 시작할때 2~9로 8개

3로 시작할때 3~9로 7개

.

.

.

9로 시작할때 9~9로 1개

 

즉

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

와 같은 점화식을 가지게 됩니다.

 

 

 

정답코드입니다. 

#include <iostream>
using namespace std;

long long dp[65][10] = { 0 };
int t = 0, n = 0;

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 = j; k <= 9; k++)
				dp[i][j] += dp[i - 1][k];
		
	cin >> t;
	while (t--) {
		cin >> n;
		long long result = 0;
		for (int i = 0; i <= 9; i++)
			result += dp[n][i];
		cout << result << '\n';
	}
}