백준 10844 쉬운 계단 수

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 n자리 숫자에서 각 인접 숫자끼리의 차이가 1 나는 숫자의 개수를 구하는 문제입니다.

 

저는 dp를 2차원 배열로 선언하고 하나의 인덱스는 자리수 그리고 나머지 하나의 인덱스는 끝자리 숫자를 나타내는 숫자를 뜻합니다.

 

이때 숫자는 0으로 시작 할 수 없고 끝자리 숫자가 0 , 9 일때는 다음에 붙는 숫자가 1과 8 만 가능합니다.

나머지 경우에는 끝자리 숫자 -1, +1 이 가능합니다.

 

dp[i][j] = (dp[i-1][j-1] + dp[i+1][j-1]) % 1000000000 따라서 끝자리 숫자가 0,9 가 아닐때는 이러한 점화식이 나오게 됩니다. 

j자리 숫자중 끝자리가 i인 숫자의 개수 = j-1자리 숫자중 끝자리가 i-1 인 숫자의 개수 + j-1자리 숫자중 끝자리가 i+1 인 숫자의 개수 라는 의미입니다.

 

계산 과정에서 10억이 넘을 수 있으므로 배열과 결과는 long long 형태로 선언 해줍니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	long long dp[10][101] = {0, };
	long long result = 0;
	for(int i = 1; i <= 9; i++)
		dp[i][1] = 1;
	
	int N; cin >> N;
	for(int j = 2; j <= N; j++)
		for(int i = 0; i <= 9; i++) {
			if(i == 9)
				dp[i][j] = dp[8][j-1] % 1000000000;
			else if(i == 0)
				dp[i][j] = dp[1][j-1] % 1000000000;
			else
				dp[i][j] = (dp[i-1][j-1] + dp[i+1][j-1]) % 1000000000; 
			}
	
	for(int i = 0; i <= 9; i++)
		result += dp[i][N];
	
	cout<< result % 1000000000;
	return 0;
}