[C++] 백준 10844번 쉬운 계단 수

 

1) 문제설명

 

백준 Online Judge 10844번 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

2) 아이디어

 

dp를 이중배열로 받아서 (i / j) 의 인덱스를 각각 (자릿수 / 마지막 수) 로 생각한다.

마지막수/ 자릿수	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2
4	3	4	7	7	8	8	8	7	6	3

마지막 수가 0 일때와 9일때를 제외한 나머지는

dp[자릿수][마지막수] = dp[자릿수-1][마지막수-1] + dp[자릿수-1][마지막수+1] 인 것을 알 수있다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
long long dp[101][101];

int main() {	
	int n;
	cin >> n;

	dp[1][0] = 0;
	dp[1][1] = 1;
	dp[1][2] = 1;
	dp[1][3] = 1;
	dp[1][4] = 1;
	dp[1][5] = 1;
	dp[1][6] = 1;
	dp[1][7] = 1;
	dp[1][8] = 1;
	dp[1][9] = 1;

	dp[2][0] = 1;
	dp[2][9] = 1;

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j + 1] % 1000000000; // 마지막 숫자가 0일 경우 
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][j - 1] % 1000000000; // 마지막 숫자가 9일 경우
			}
			else if(j >= 1 && j <= 8){ 
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
			}

		}
	}

	long long sum = 0;
	for (int i = 1; i <= n; i++) {
		sum = 0;
			for (int j = 0; j <= 9; j++) {
				sum = sum + dp[i][j];
			}
	}
	cout << sum%1000000000 << endl;
}

dp문제는 생각하기가 정말 어렵다.