백준 / 다이나믹 프로그래밍 / 10844번 / 쉬운 계단 수 / C++

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17

 

#include <iostream>
using namespace std;

const int N = 1e2 + 1;
const int divisor = 1e9;

long long dp[N][10] = {0,};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	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];
			}
			else if(j>=1 && j<=8) {
				dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
			}
			else if(j == 9) {
				dp[i][j] = dp[i-1][j-1];
			}
			dp[i][j] %= divisor;
		}
	}
	
	long long result = 0;
	
	for(int i=0; i<=9; i++) {
		result += dp[n][i];
		result %= divisor;
	}
	
	cout << result << '\n';
	
	return 0;
}

---

dp(dynamic programming)문제는 항상 느끼지만 처음에 자료구조를 어떻게 짤지가 정말 중요한것 같다.

일단 dp배열은 2차원 배열의 형태이다.

dp[i][j]가 있다고 하면, i는 수의 길이를 나타내는 것이고, j는 그 수가 어떤수로 끝나는지를 나타내준다.

 

예를들어 dp[2][5]가 있다면 입력값의 길이는 2이고, 그 수는 5로 끝난다.

따라서 45나 65밖에 올수가 없으므로 dp[2][5]에는 2를 할당해준다.

 

dp[2][5]를 나타내기 위한 알고리즘을 생각해보자.

숫자의 길이는 총 2이다.

그러면 마지막숫자가 5가 오고, 계단수여야 하려면 첫번째 숫자는 4나 6밖에 올 수가 없다.

4나 6은 dp[1][4] 와 dp[1][6]으로 나타낼 수 있다.

 

다시말해 설명하자면, dp[2][5]는 4로끝나는 계단수뒤에 5가 오거나, 6으로 끝나는 계단수뒤에 5가 와야 한다는 소리다.

따라서 우리는 dp[i][j]를 dp[i-1][j-1] + dp[i-1][j+1]로 나타낼 수 있다.

 

하지만 0과 9로 끝나는 경우는 위가 성립하지 않는다.

0으로 끝나는 경우(j == 0)에 dp[i-1][j-1]을 하게되면 dp[i-1][-1]이 되므로 에러가 발생한다.

따라서 0으로 끝나는 경우는 dp[i-1][j+1]만 해주면 된다.

 

9로 끝나는 경우는 dp[i-1][8]과 dp[i-1][10]을 생각해야 하는데,

10으로 끝나는 경우는 0으로 끝나는 경우와 같으므로 해주지 않아도 된다.

따라서 dp[i-1][j-1]만 해주면 된다.