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

문제

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

10844번: 쉬운 계단 수

---

문제 요약

각 자릿수와 인접한 모든 자릿수의 차이가 1인 수를 계단 수라고 한다.

 

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 출력한다.

 

+ 0으로 시작하는 수는 계단 수가 아니다.

---

코드

#include <iostream>

#define ll long long
using namespace std;

int n;

ll dp[101][10]; // dp[i][j]: 길이가 i인 계단수 중 j로 끝나는 수의 개수

int main() {
	cin >> n;

	// dp 초기값 (길이가 1인 계단 수들)
	for (int i = 1; i < 10; i++) {
		dp[1][i] = 1;
	}

	// 길이가 2이상인 계단수들
	for (int i = 2; i <= 100; i++) {
		for (int j = 1; j < 9; j++) {
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
		}
		dp[i][0] = dp[i - 1][1] % 1000000000;
		dp[i][9] = dp[i - 1][8] % 1000000000;
	}

	ll res = 0;
	for (int i = 0; i < 10; i++) {
		res += dp[n][i];
	}
	res %= 1000000000;

	cout << res;
}

---

코드 설명

dp[i][j]: 길이가 i인 계단 수 중, j로 끝나는 수의 개수

 

먼저, dp테이블의 초기값 설정을 위해 0 ~ 9에 대한 dp 값을 채운다.+ 0은 계단 수가 아님에 유의한다.

 

길이가 i인 수 중 j로 끝나는 수의 개수 

 

= 길이가 i - 1인 수 중 j -1 로 끝나는 수 끝에 j를 붙인 수 + 길이가 i - 1인 수 중 j + 1로 끝나는 수 끝에 j를 붙인 수

 

=> dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

 

+ j가 0과 9인 경우는 j - 1, j + 1 둘 중 하나만 고려한다.

 

dp[n][0 ~ 9]를 더한 결과를 1,000,000,000으로 나눈 값을 출력한다.