[백준문제풀이] 10844 쉬운 계단 수

 

풀이일시 : 2020-12-28

 

 

문제 : 

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

 

입력 : 

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

ex) 2

 

 

출력 :

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

ex) 17

 

 

풀이 : 

DP문제이다. 즉 점화식을 세워봐야한다. 

 

dbstndi6316.tistory.com/35

[개념정리] DP 동적프로그래밍

입력받은 수 까지 DP를 수행해주면 될 것이다.

 

DP[i][j] 에서 i는 입력받은 수 (수의 길이를 나타냄), 즉 DP시 1에서부터 N까지 하나씩 올라갈 수이다.

 

j는 맨 끝수를 뜻한다. 만약 j가 0이라면 DP[i][j]에는 DP[i-1]번째에서 [j+1]번째의 수를 받을것이다.

 

예를들면 이전 DP의 1에의 경우의 수를 그대로 받는다는 의미로, 확장이 불가하다는 뜻이다.

 

좀더 쉽게 풀이하면 0은 붙어있는 수가 -1과 1인데 -1로는 뻗어갈 수 없으니 1로만 확장한다.

 

마찬가지로 9는 8과 10으로 뻗어갈 수 있는데 10으로는 뻗을 수 없기때문에 8로만 뻗어나간다.

 

이외의 경우에는 전부 두 가지로 뻗어나갈 수 있을것이다.

 

전부 수행한 후 sum하여 출력한다.

 

//점화식 세우는데서 문제
//long long 형에서 문제

#include <iostream>

using namespace std;
const int MAX = 101;

int N;
long long DP[MAX][10];
long long sum = 0;

//점화식을 세우자

void solution(int n) {

	DP[1][0] = 0;
	for (int i = 1; i <= 9;i++) {
		DP[1][i] = 1;
	}

	for (int i = 2; i <= n; i++) { //길이
		for (int j = 0; j <= 9; j++) {
			if (j == 0) {
				DP[i][j] = DP[i - 1][j + 1]%1000000000;
			}
			else if (j == 9) {
				DP[i][j] = DP[i - 1][j - 1]%1000000000;
			}
			else
				DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1])%1000000000;
		}
	}
	
	for (int i = 0; i <= 9; i++) {
		sum += DP[n][i];
	}
}

int main() {
	cin >> N;
	solution(N);
	cout << sum%1000000000<<'\n';
	return 0;
}