10844번: 쉬운 계단 수

문제:

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력:

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

풀이:

• 이 문제는 바텀업 방식으로 아래서부터 경우의 수를 쌓아올리면서 풀었다. 이 문제를 풀기 위한 핵심은 이전 단계의 어떤 숫자의 끝자리로 지금 내 숫자를 만들 수 있는지 이다.
• 우선 입력값(수의 길이)의 크기와 0부터 9까지 끝자리의 숫자를 표현하기 위해 10의 크기를 가진 2차원 배열 d[입력값+1][10]을 만들어준다. 이제 쌓아 올리기를 시작하면 된다. 우선 base case인 1인 경우에는 0을 빼고 모든 값은 경우의 수가 1이기 때문에 1로 초기화 해준다.
• 이제 2부터 쌓아올리기 위한 for문을 만든다. 그리고, 2중 for문으로 끝자리가 0부터 9까지인 경우를 모두 기록 해야 된다. 이제 끝자리가 0인 경우와 9인 경우는 이전의 끝자리가 1인 경우와 8인 경우 밖에 없기 때문에 0인 경우는 +1을 하여 1인경우와 9인 경우는 -1을 하여 8인 경우를 예외 처리를 해준다. 나머지 경우에는 현재 끝자리 숫자를 만들 수 있게 현재 끝자리 수에 -1과 +1한 이전 값일 때의 경우의 수를 더해 준다. 또한, 구한 값을 1,000,000,000의 나머지로 저장 해주는 것도 잊지 말자.
• 0부터 9까지 끝자리를 가진 모든 경우의 수를 더 해준 뒤 정답을 출력 해준다.

코드:

#include <iostream>
#define MOD 1000000000

using namespace std;

int main(){
	int n, answer = 0;
	//입력 
	cin >> n;
	long long d[n+1][10];
	//Base case 초기화 
	for(int i = 0; i <= 9; i++){
		if(i==0) d[1][i] = 0;
		else d[1][i] = 1;
	}
	//2부터 n까지 모든 경우의 수 구함 
	for(int i = 2; i <= n; i++){
		//끝에 자리마다 경우의 수 기록 
		for(int j = 0; j <= 9; j++){
			if(j == 0) d[i][j] = (d[i-1][j+1])%MOD; //끝에 자리가 1인 경우 
			else if(j == 9) d[i][j] = (d[i-1][j-1])%MOD; //끝에 자리가 9인 경우 
			else d[i][j] = (d[i-1][j-1] + d[i-1][j+1])%MOD; //나머지 경우 
		} 
	}
	//정답 합산 
	for(int i = 0; i <= 9; i++) answer = (answer+d[n][i])%MOD;
	//출력 
	cout << answer;
}