10844 쉬운 계단 수 (동적계획법) [Silver I]

10844번: 쉬운 계단 수 (acmicpc.net)

 

길이가 N인 계단 수의 개수가 몇개인지 물어보는 문제입니다.

계단수 예시) 456789, 4565656, 1212321234321

 

풀이법

이 문제는 조합식 찾는데에 있어서 난이도가 높았던 문제입니다.

경우의 수가 너무 많아서 예시를 적어보는것도 힘들었네요

 

10진수를 이용해서 예시를 만들면 보기 안좋아서

3진수(0~2)로 예시를 만들어봤습니다. 

 

길이에 따라 계단 수 끝에 0, 1, 2가 올 경우의 수 표입니다.

 

계단 수는 1차이가 나는 수

즉 "현재 끝에 있는 수" 에서 "-1 혹은 +1을 한 수"를 사용할 수 있습니다.

그래서 끝이 0이면 다음 수에서는 1로 움직일 수 있으니 끝이 1일 경우의 수 + 1이 되고

끝이 1이면 다음 수 에서는 0, 2로 움직일 수 있으니 끝이 0, 2일 경우의 수 +1이 됩니다.

 

그렇기 때문에 조합식을 만든다면

array[높이][현재 수] = array[높이 - 1][현재 수-1] + array[높이 - 1][현재 수 + 1];

로 만들 수 있겠습니다.

0과 2는 옆에 하나의 수 밖에 없기 때문에 주의해서 코딩하면 되겠습니다.

 

정답 코드입니다.

#include <iostream>
using namespace std;
 
static int N;
static long long D[101][10];
const long mod = 1000000000;

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

	cin >> N;

	for (int i = 1; i < 10; i++)
		D[1][i] = 1;
	 
	for (int i = 2; i <= N; i++)
	{
		D[i][0] = D[i - 1][1];
		D[i][9] = D[i - 1][8];

		for (int j = 1; j < 9; j++) {
			D[i][j] = (D[i - 1][j - 1] + D[i - 1][j + 1]) % mod;
		}
	}

	long sum = 0;
	for (int i = 0; i < 10; i++)
		sum = (sum + D[N][i]) % mod;

	cout << sum;
}