[👊DP뿌시기 #4] (BOJ 10844) 쉬운 계단 수

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

 

---

접근법

일단 N=1 ~ N=3일때 까지 무작전 모든 경우의 수를 생각해보자

DP[2]는 DP[1]에서 증가한 경우와 DP[1]에서 감소하는 경우로 나눌 수 있다.

DP[3]도 마찬가지로 DP[2]에서 증가하는 경우와 감소하는 경우로 나눌 수 있다.

 

그래서 처음에는 밑의 식처럼 생각을 했다.

 

 

너무 당연하게 생각했는지 틀렸다.

해당 접근이 왜틀렸는지 조금 더 공부해야하겠다...

 

이번에도 매우 많은 케이스가 주어지기 때문에 이를 이차원배열 DP로 풀면 좋을것 같다고 생각햇다.

 

DP[i][j]에서 i는 수의 크기를, j는 끝자리 수를 의미한다.

 

위에서 구한 수를 배열에 저장하게 되면 이런식으로 나온다.

여기서 규칙을 생각해보자.

 

일단 특수한 경우인 0과 9를 먼저 보자

0은 이전 숫자가 무조건 1이어야 하기 때문에 D[2][0] = D[1][1] 이게 된다.

 

9의 경우도 비슷하게 이전 숫자가 무조건 8이어야한다.

따라서, D[2][9] = D[1][8] 이다.

 

나머지 숫자의 경우, 7을 예로 들면

7이전에는 6과 8이 올 수 있기 때문에

D[2][7] = D[1][6] + D[1][8] 이된다.

 

도출된 점화식을 토대로 코드를 작성해보자.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 101
#define ll long long

ll dp[MAX][10];

void init() {
	for (int i = 1; i < 10; i++) {
		dp[1][i] = 1;
	}
}

void Print(int n) {
	ll sum = 0;
	for (int i = 0; i <= 9; i++) {
		sum += dp[n][i];
	}
	cout << sum % 1000000000;
}

int main() {
	int n;
	cin >> n;
	init();
	
	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]; // 1,1ㅇㄴ 것에 0붙인 거라
			else if (j == 9)
				dp[i][j] = dp[i - 1][j - 1]; // 1,8인 것에 9붙인 거라 
			else
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
			dp[i][j] %= 1000000000;
		}
	}


	Print(n);

	
	
}