[백준 / C언어] 10844번: 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

난이도: solved.ac 실버 1

 

 

dp 문제다

 

점화식을 세우기 위해 N = 1일 때부터 차례로 해보자

 

N = 1일 때,

 

1, 2, 3, 4, 5, 6, 7, 8, 9로 길이가 1인 쉬운 계단 수는 9개가 된다

 

N = 2일 때,

 

10
12
21​
23
32
34
43
45
54
56
65
67
76
78
87
89
98

 

로 17개가 되는데, 눈치채셨을까?

 

길이가 N인 i로 끝나는 쉬운 계단 수는 길이가 N - 1인 i - 1로 끝나는 쉬운 계단 수와 i + 1로 끝나는 쉬운 계단 수에 i를 붙여 만들어진다

 

그림을 나타내면 아래와 같다

 

 

그림을 보면 알겠지만 주의할 점이 있는데, 0으로 끝나는 경우와 9로 끝나는 경우 조금 다르다

 

길이가 N인 0으로 끝나는 수와 9로 끝나는 수는 각각 길이가 N - 1인 수에서 1로 끝날 때, 8로 끝날 때에서만 만들어진다

 

즉,

(길이가 N이고 i로 끝나는 쉬운 계단 수를 나타내는 경우의 수)

= (길이가 N - 1이고 i - 1로 끝나는 쉬운 계단 수를 나타내는 경우의 수) + (길이가 N - 1이고 i + 1로 끝나는 쉬운 계단 수를 나타내는 경우의 수)

(단, i = 1, 2, 3, ... , 7, 8)

 

(길이가 N이고 0으로 끝나는 쉬운 계단 수를 나타내는 경우의 수)

= (길이가 N - 1이고 1로 끝나는 쉬운 계단 수를 나타내는 경우의 수)

 

(길이가 N이고 9로 끝나는 쉬운 계단 수를 나타내는 경우의 수)

= (길이가 N - 1이고 8로 끝나는 쉬운 계단 수를 나타내는 경우의 수)

가 된다

 

이를 2차원 dp 배열로 나타내면 아래와 같다

 

dp[i][1]: 길이가 N이고 i로 끝나는 쉬운 계단 수를 나타내는 경우의 수

dp[i][0]: 길이가 N - 1이고 i로 끝나는 쉬운 계단 수를 나타내는 경우의 수

 

dp[i][1] = dp[i - 1][0] + dp[i + 1][0]        (단, i = 1, 2, 3, ... , 7, 8)

dp[0][1] = dp[1][0]

dp[9][1] = dp[8][0]

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int dp[10][2];
// dp[i][1]: i로 끝나는 수를 나타내는 경우의 수
// dp[i][0]: 이전 자릿수가 i로 끝나는 수를 나타내는 경우의 수

int main() {
	int N, i, ans = 0;
	scanf("%d", &N);

	for (i = 1; i < 10; i++)
		dp[i][0] = 1;

	while (N > 1) {
		dp[0][1] = dp[1][0];
		for (i = 1; i < 9; i++) {
			dp[i][1] = (dp[i - 1][0] + dp[i + 1][0]) % 1000000000;
		}
		dp[9][1] = dp[8][0];

		for (i = 0; i < 10; i++)
			dp[i][0] = dp[i][1];
		N--;
	}

	for (i = 0; i < 10; i++)
		ans = (ans + dp[i][0]) % 1000000000;
	
	printf("%d", ans);
	return 0;
}