C++ 백준 10844번

계속 다이나믹 프로그래밍에 대해서 풀어보고 있다!!

 

백준 10844번 www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

문제 : 45656이란 수를 보자.

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

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

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

 

인접한 모든 자릿수의 차이가 1이 나야 되니까 마지막 수가 i라면 그 앞에는 i-1이나 i+1이 있을 것이다! (단. i 가 1이면 앞에는 무조건 2이고 9라면 무조건 8일 것이다)

그래서 길이가 n이고 마지막 수가 i인 계단수의 개수를 d[n][i]라고 한다면

d[n][i] = d[n-1][i-1] + d[n-1][i+1] 로 표현할 수 있다.

 

#include<iostream>
using namespace std;

long long d[101][10];
long long mod = 1000000000;

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= 9; i++) {
		d[1][i] = 1; // i로 끝나는 길이 1인 계단 수는 한개
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			d[i][j] = 0; // 0으로 초기화
			if (j - 1 >= 0) { //j-1==0 이면 d[i-1][j-1] = 0이니까 더해줘도 노상관
				d[i][j] += d[i - 1][j - 1];
			}
			if (j + 1 <= 9) {
				d[i][j] += d[i - 1][j + 1];
			}
			d[i][j] %= mod; 
		}
	}
	long long ans = 0;
	for (int i = 0; i <= 9; i++) {
		ans += d[n][i];
	}
	ans %= mod;
	cout << ans << '\n';
}

100000000으로 나눠줘야 하는 거 잊지 말자!!