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

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

10844번: 쉬운 계단 수

---

문제 접근

 계단 수는 마지막에 오는 숫자에 따라서 다음에 올 수 있는 숫자가 정해져 있다.

예를 들어서 0 뒤에는 무조건 1, 9 뒤에는 무조건 8이 와야 한다.

그 외에 숫자들은 +1 값과 -1 값이 올 수 있다. (ex. 2 → 1 or 3)

배열 DP는 숫자의 길이와 마지막 수를 인덱스로 가지고 해당 숫자의 길이의 마지막 숫자에 대한 경우의 수를 저장한다.

DP [2][3]은 즉, 길이가 2인 숫자의 마지막 숫자가 3의 경우의 수를 저장하고 있다.

 

 DP[i][j]를 점화식으로 표현하면 

j가 0이면, DP[i][j] = DP[i-1][j+1]

j가 9이면, DP[i][j] = DP[i-1][j-1]

그 외에 숫자는, DP[i][j] = DP[i-1][j+1] + DP[i-1][j-1] 이다.

 

숫자의 길이가 조금만 커져도 값이 너무나도 커지기 때문에 중간중간에 1,000,000,000으로 계속 중간 연산을 해줘야 결괏값을 출력할 때 문제가 없다.

느낀 점

문제를 보자마자 바로 다음에 올 숫자에 따라 정해진 점을 알았지만 그것을 구현하는데 많이 어려워했다. 계속 DPS로 구현하는 방법만 생각이 나서 고생했지만 2차원 배열로 해결하면 쉬운 점을 알고 나선 쉽게 접근했다.

코드

#include <iostream>
using namespace std;

int n, sum = 0;
int dp[101][10] = { 0, };

int main() {
	cin >> n;
	for (int i = 1; i < 10;i++) {
		dp[1][i] = 1;
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j + 1];
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
			dp[i][j] %= 1000000000;
		}
	}

	for (int i = 0; i < 10;i++) {
		sum = (sum + dp[n][i]) % 1000000000;
	}
	cout << sum;
}