10844번: 쉬운 계단 수(백준 C++)

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

코드

#include <iostream>
using namespace std;

int n;
int answer = 0;
int stair[10] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int dp[10];

void solve(){
	for(int i=2; i<=n; i++){
		for(int j=0; j<10; j++){
			if(j == 0) dp[0] = stair[1];
			else if(j == 9) dp[9] = stair[8];
			else dp[j] = stair[j-1] + stair[j+1];
			dp[j] %= 1000000000;
		}
		for(int k=0; k<10; k++){
			stair[k] = dp[k];
		}
	}
	for(int j=0; j<10; j++){
		answer += stair[j];
		answer %= 1000000000;
	}
	cout << answer;
}

int main() {
	cin >> n;
	solve();
	return 0;
}

문제

인접한 모든 자리수의 차이가 1이 나는 N자리의 수가 몇 개인지 구하는 문제입니다.

45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

풀이

 

인접한 모든 자리수의 차이가 1.

여기서 우리는 점화식을 생각해 볼 수 있습니다.

N자리 수는, N-1자리 수의 마지막 수와 차이가 1 나는 수를 붙인 수라는 것이죠.

N = 5
ex) 45656 

N =6
                 45656(6-1) -> 456565
45656
                 45656(6+1) ->456567

 

1 차이씩 이면, 마지막 수 + , -  1 이니까, 이전 자리수 X 2 하면 되나요?

아닙니다. 고려해야 할 부분이 몇 가지 더 있습니다.

1. 0으로 시작하는 수는 없다.
2. 마지막 자리가 0인 경우에는 다음에는 1밖에 올 수 없다.
3. 마지막 자리가 9인 경우에는 다음에는 8밖에 올 수 없다.

그렇기 때문에 길이가 10인 배열을 한 번 만들어 보도록 하겠습니다.

이는, N자리의 수에서 마지막 자리 수에 있는 수의 개수를 나타내는 건데요

N = 1일때는 아래와 같습니다.

N = 1이면 1 2 3 4 5 6 7 8 9 이렇게  9개입니다.

마찬가지로 마지막 자리 수도 1~9까지 각 1개씩 있으므로 위의 그림과 같습니다.

그럼 N = 2 에서는 어떻게 될까요?

 

• 마지막 자리가 0이 되기 위해서는 이전 마지막 수가 1이어야 한다.

• 마지막 자리가 1이 되기 위해서는 이전 마지막 수가 0 또는 2이어야 한다.

• 마지막 자리가 2이 되기 위해서는 이전 마지막 수가 1또는 3이어야 한다.

• 마지막 자리가 3이 되기 위해서는 이전 마지막 수가 2 또는 4이어야 한다.

• 마지막 자리가 4이 되기 위해서는 이전 마지막 수가 3 또는 5이어야 한다.

• 마지막 자리가 5이 되기 위해서는 이전 마지막 수가 4 또는 6이어야 한다.

• 마지막 자리가 6이 되기 위해서는 이전 마지막 수가 5 또는 7이어야 한다.

• 마지막 자리가 7이 되기 위해서는 이전 마지막 수가 6 또는 8이어야 한다.

• 마지막 자리가 8이 되기 위해서는 이전 마지막 수가 7 또는 9이어야 한다.

• 마지막 자리가 9이 되기 위해서는 이전 마지막 수가 8이어야 한다.

 

위의 조건에 따라 N = 2 일때는 17개를 갖게 됩니다.

이러한 방식으로 점화식을 작성하시면 문제풀이를 하실 수 있습니다.