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

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

10844번: 쉬운 계단 수

 

dp로 해결하는 문제이다. 계단수를 구하기 위해 x로 끝나는 수를 계산할 필요가 있어보여 2차원 배열로 dp[i][10]을 만들어 주었다.

n = 1 9

n = 2 17

 

이전에 1로 끝나는 숫자가 있다면 그 뒤에 0과 2가 붙으면 되므로 그 값을 증가시켜준다. 하지만 9로 끝나는 숫자는 8은 뒤에 붙을 수 있지만 0은 뒤로 못 붙으므로 이를 예외처리 해준다.

 

또한 두자리 숫자부터 0이 생기므로 이 또한 초반에 따로 처리해준다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[101][10] = { 0, };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	for (int i = 1;i <= 9;i++) {
		dp[1][i] = 1;
	}
 
	int n;
	cin >> n;
 
	for (int i = 2;i <= n;i++) {
		for (int j = 0;j <= 9;j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][1] % 1000000000;
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][8] % 1000000000;
			}
			else {
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
			}
		}
	}
 
	long long ans = 0;
	for (int i = 0;i < 10;i++) {
		ans = (ans + dp[n][i]) % 1000000000;
	}
 
	cout << ans << "\n";
 
	return 0;
}

 

전체 코드는 이와같다.

 

생각나는데로 바로 코딩하는것 보다 한번 이렇게 블로그에 경우의 수를 정리한다음 코딩을 하는게 오류가 날 확률도 적고 빨리 푸는거 같다는 생각이 드는 문제였다.