[Baekjoon] 10844 - 쉬운 계단 수 (C++)

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

10844번: 쉬운 계단 수

여러 문제를 풀다 보니 이제 슬슬 DP(dynamic programming)에 익숙해지는 것 같습니다. 이번 문제도 DP를 이용한 문제입니다. 처음에는 N에 따라서 계단 수의 개수 규칙을 바로 찾으려고 했지만, 2차원 배열을 사용해 전체 개수가 아닌 각 첫째 자릿수의 개수를 찾는 방식으로 쉽게 풀 수 있었습니다.

 

먼저 예를 들어 볼까요? N이 1인 경우에서 3인 경우까지 직접 모든 경우의 수를 나열해 보겠습니다.

 

N = 1	N = 2	N = 3
1	10, 12	101, 121, 123
2	21, 23	210, 212, 232, 234
3	32, 34	321, 323, 343, 345
4	43, 45	432, 434, 454, 456
5	54, 56	543, 545, 565, 567
6	65, 67	654, 656, 676, 678
7	76, 78	765, 767, 787, 789
8	87, 89	876, 878, 898
9	98	987, 989
총 9개	총 17개	총 32개

규칙이 보이시나요? 하나의 수에서 만들어지는 계단 수가 2개임을 알 수 있습니다. 단, 첫째 자리가 0 또는 9인 경우에 이로부터 만들어지는 수는 1개임을 알 수 있죠. 표에 빨간색으로 표시된 수는 첫째 자리가 0 또는 9인 수이고, 파란색으로 표시된 수는 이로부터 만들어진 수를 의미합니다.

 

이 부분에 유의해서 2차원 배열로 DP를 하면 되겠습니다. 첫째 자릿수의 개수를 확인하고 새로 만들어지는 수의 첫째 자릿수를 계속해서 기록하는 방식으로 푸시면 됩니다. 하지만 주의할 점이 있는데 정답을 출력할 때 1,000,000,000으로 나눈 나머지를 출력하라고 되어 있습니다. 이 이유는 N이 커질수록 경우의 수가 굉장히 많아지기 때문입니다. 그렇기에 정수 오버플로가 발생하지 않도록 구하는 과정에서 나머지를 계속해서 구해줘야 됩니다.

#include <iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	unsigned int dp[100][10] = { 0, };
	unsigned int answer = 0;

	// 초깃값 설정 (동적 계획법)
	// 수의 길이가 1인 경우 0을 제외한 나머지 수의 개수를 1로 설정
	for (int i = 1; i < 10; i++) {
		dp[0][i] = 1;
	}

	// 수의 길이를 늘려가면서 계단 수의 개수를 찾음
	// 첫째 자릿수의 개수를 기준으로 계단 수를 만들어 감
	for (int i = 1; i < n; i++) {
		// 0 또는 9인 경우 만들 수 있는 경우의 수가 1개
		dp[i][1] = dp[i - 1][0];
		dp[i][8] = dp[i - 1][9];
	
		// 1부터 8인 경우 만들 수 있는 경우의 수가 2개
		for (int j = 1; j < 9; j++) {
			dp[i][j - 1] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
			dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j]) % 1000000000;
		}
	}

	// 첫째 자릿수를 기준으로 만들어진 계단 수의 개수를 모두 더함
	for (int i = 0; i < 10; i++) {
		answer = (answer + dp[n - 1][i]) % 1000000000;
	}

	cout << answer << "\n";
	return 0;
}