쉬운 계단 수

알고리즘 구분 : 다이나믹 프로그래밍

문제

45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

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

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

예제 입력 1
1
예제 출력 1
9
예제 입력 2
2
예제 출력 2
17

문제 풀이

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n;
long long result = 0;
long long dp[101][10];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	dp[1][0] = 0;
	for(int i = 1; i < 10; i++) {
		dp[1][i] = 1;
	}
	
	for(int i = 2; i < 101; i++) {
		dp[i][0] = (dp[i - 1][1]) % 1000000000;
		for(int j = 1; j < 9; j++) {
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;	
		}
		dp[i][9] = (dp[i - 1][8]) % 1000000000;		
	}
	
	for(int i = 0; i < 10; i++) {
		result += dp[n][i];
	}
	result %= 1000000000;
	
	cout << result << endl;
	
	return 0;
}

• 문제 출처 : https://www.acmicpc.net/problem/10844
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.