[백준] 쉬운 계단 수 ( 10844번)

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

---

약간은 귀찮아 보이는 dp 문제이다.

 

계단수란 1씩 차이가 나는 수이다.

마지막 자리수가 1이라면 그 앞에 올 수 있는 수는 0과 2이다. 

만약 0이라면 그 앞엔 1밖에 올 수 없고 마찬가지로 9라면 8밖에 올 수 없다.

나머지는 두개씩 올 수 있지만 저 둘만 한개씩 올 수 있다. 

이를 유의하며 점화식을 세워보자.

 

dp[N][i] : N자리 수에 맨 끝자리 수를 i로 두는 방법이라고 해보자. 위의 예외를 생각해보면, 

dp[N][0] = dp[N-1][1]이고 dp[N][9] = dp[N-1][8]이다.

나머지는 dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1]이 될 것이다.

이 식에 맞춰 문제를 풀면 된다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%89%AC%EC%9A%B4%20%EA%B3%84%EB%8B%A8%20%EC%88%98%20(10844%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
using namespace std;
int dp[101][11];
int N;

int main() {
	cin >> N;
	for (int i = 0; i <= 9; i++) dp[1][i] = 1;
	for (int i = 2; i <= N; i++) {
		dp[i][0] = dp[i - 1][1] % 1000000000;
		dp[i][9] = dp[i - 1][8] % 1000000000;
		for (int j = 1; j <= 8; j++)
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
	}
	
	long long res = 0;
	for (int i = 1; i <= 9; i++) 
		res = (res + dp[N][i]) % 1000000000;

	cout << res;
}