[백준BaekJoon]10844: 쉬운 계단 수/C++

문제

45656이란 수를 보자.

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

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

---

코드

이전에 나온 값들을 이용하여 다음 값을 도출해내는 DP문제이다.

#include <bits/stdc++.h> 
using namespace std;

int DP[101][10];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	long long  ans = 0;
	int N;
	cin >> 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 < 10; j++) {

			if (j == 0)DP[i][j] = DP[i - 1][1];
			else if (j == 9)DP[i][j] = DP[i - 1][8];
			else DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1];

			DP[i][j] %= 1000000000;
		}

	}

	for (int i = 0; i < 10; i++) {
		ans += DP[N][i];
		ans %= 1000000000;
	}

	cout << ans;
}

이차원 배열은 [길이가 i(N)일 때][마지막 자리수가 j인] 수의 개수를 담고 있다.

보통의 경우는 자리 차이가 나는 수가 2개여서 앞, 뒤 값을 더해주는데 

뒷자리가 0과 9의 경우에는 이전 계단수의 뒷자리가 1과 8일 경우에만 발생하니 이전 값을 그대로 가져온다.

 

이렇게 증가하다 보면 값이 커지기 때문에, 계산할 때마다 1000000000를 나누어 준다.

 

 

끝....쉬운 계단 수(쉽지 않음)