문제 출처

1. 문제설명

• 계단 수란 인접한 모든 자리에 차이가 1인 수를 말한다.
• N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하라
• 0으로 시작하는 수는 계단 수가 아니다.

2. 알고리즘 설계

• DP 방식으로 풀이할 수 있었다.
  • 사실 문제를 보기만 해도 이건 DP였다.
• 우선, 숫자를 한 개 놓는 경우를 생각해보자.
  • 0으로 시작할 수 없으니, 1부터 9까지 1개의 경우의 수가 있을 것이다.
• 숫자를 2개 놓는 경우는, 0 또는 9의 처리가 필요하다.
  • 숫자가 0이라면 -1을 하는 경우 -1이 되므로 계단수가 될 수 없다.
  • 숫자가 9라면 +1을 하는 경우 10이 되므로 10진법에 위배된다.
• 상기 두 가지 처리를 하게 되면 아래와 같다.
  • if(j != 0) DP[i][j] += DP[i-1][j-1]
  • if(j != 9) DP[i][j] += DP[i-1][j+1]
• N의 크기가 100보다 작거나 같지만, 일부 범위를 넘어서면 경우의 수가 매우 커질 수 있다.
  • 값을 갱신해줄 때마다 주어진 숫자로 나눠준다.
  • 처음에 이거 안해줘서 맞왜틀 시전해버렸다…

3. 전체 코드

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

const int DIV = 1000000000;
int n, DP[105][10];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;

	for(int i=1; i<10; 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][j-1];
			if(j != 9) DP[i][j] += DP[i-1][j+1];
			DP[i][j] %= DIV;
		}
	}

	long long ans = 0;
	for(int i=0; i<10; i++) ans += DP[n][i];

	cout << ans % DIV;
	return 0;
}