[BOJ] 백준 10844번: 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

기본적인 DP 문제입니다.

 

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

const int MOD = 1000000000;
int N, dp[101][10], res;

void solve(){
	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 = 1; j <= 8; ++j){
			dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % MOD;
		}
		dp[i][0] = dp[i-1][1];
		dp[i][9] = dp[i-1][8];
	}
	
	res = 0;
	for(int i = 0; i <= 9; ++i){
		res = (res + dp[N][i]) % MOD;
	}
	cout << res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	solve();
}

 

"dp table의 차원을 늘림으로써 case 분류하기"를 연습할 수 있는 좋은 문제라고 생각합니다.

 

이번에도 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 dp 문제를 풀이하겠습니다.

 

1) table 정의

dp[i][j] : 숫자 j로 끝나는 길이가 i인 계단 수의 개수 (j = 0, 1, 2, ... 9)

 

2) 점화식 찾기

1 ≤ j ≤ 8일 때 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; 

dp[i][0] = dp[i-1][1];

dp[i][9] = dp[i-1][8];

 

3) 초기값 설정

dp[1][0] = 0;

dp[1][1~9] = 1;

 

주의할 점

무심코 답을 계산할 때 res += dp[N][i]; 로 계산한다면 integer overflow가 발생할 수 있습니다.

더할 때마다 문제에서 주어진 값으로 나눈 나머지를 저장해야 합니다. 

 

시간복잡도는 O(N)입니다.