BaekJoon(10844)::쉬운 계단 수

문제

10844번: 쉬운 계단 수

문제 파악

여기서 쉬운 계단수란?

'인접한 모든 자리의 차이가 1'인 수를 말한다.

 

N이 주어졌을때, 길이가 N인 쉬운 계단 수가 몇개 있는지 구하는 문제이다.

여기서 주의할점은 숫자의 길이가 100자리를 넘는다는 점과 0으로 시작하는 수는 계단수가 아니라는 점이다

문제 풀이

해당 문제의 진행을 다음과 같다.

결국 N자리의 수에서의 계단수의 갯수는 N-1번째 계단의 수에서 결정이 된다.

이유를 잘생각해보면 N자리의 마지막 수는 N-1번째 계단수의 마지막수와 차이가 1일 수 밖에 없기 때문이다.

이러한 점을 잘 생각해보면 다음과 같은 식을 구할 수 있다.

 

끝자리의 값이 무엇이나에 따라 식이 조금 달라지는데 해당 식은 다음과 같다.

• 0 인 경우 : DP[N][0] = DP[N-1][1]
• 9 인 경우 : DP[N][9] = DP[N-1][8]
• 1~8인 경우 :  DP[N][i] = DP[N-1][i-1] + DP[N-1][i+1]

#include<iostream>
using namespace std;

int main() {
	long dp[101][10];
	
	dp[1][0] = 0;
	for (int i = 1;i < 10;i++) {
		dp[1][i] = 1;
	}

	for (int n = 2; n <= 100; n++) {
		dp[n][0] = dp[n - 1][1];
		dp[n][9] = dp[n - 1][8];

		for (int i = 1;i < 9;i++) {
			dp[n][i] = (dp[n - 1][i - 1] + dp[n - 1][i + 1]) % 1000000000;
		}
	}

	int n;
	cin >> n;

	long sol = 0;
	for (int i = 0;i < 10;i++) {
		sol += dp[n][i];
	}

	cout << sol % 1000000000 << endl;

	return 0;
}

주의할 점

0으로 시작되는 수는 쉬운계단 수가 아니라는 점, MOD 1000000000를 적절한 위치에서 해주는 법을 이해할 필요가 있다.