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

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

10844번: 쉬운 계단 수

---

 

dp문제!

 

i \ j	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
2	2

dp[i][j]에서 i는 자릿수를, j는 시작 숫자를 의미한다.

예시 - dp[2][4] : 4로 시작하는 2자리 숫자. 총 2개 (43,45)

 

1) 한자리 숫자는 모두 계단수

 

2) n자리 숫자

• 1로 시작

 - 10xxxx... , 12xxxx... 두가지 경우 가능

 - 전자의 경우, 계단수를 만드려면 101xxxx... 가 되어야 함

 - 따라서 경우의 수는 1로 시작하는 n-2자리 숫자의 개수인데 이 값이 dp[i-2][0]임

 

 - 후자의 경우의 수는 2로 시작하는 n-1자리 숫자의 개수인데 이 값은 dp[i-1][1]임

 

 - 따라서 1로 시작하는 n자리 숫자의 계단수는 dp[i][0] = dp[i-2][0] + dp[i-1][1]

 

 - 두자리 숫자일 경우, 1로 시작하는 0자리 숫자 못구한다. 따라서 이 경우에만 따로 구해서 채워준다.

 - 1로 시작하는 두자리 숫자의 계단수는 10, 12 두가지가 가능하므로 2이다

• 2~8로 시작

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

• 9로 시작

 - 98xxxx... 만 가능. 따라서 dp[i][j] = dp[i-1][7]

 

 

#include <iostream>
using namespace std;

int main(){
	int c = 1000000000;

	int n; cin>>n;
	int dp[n][9];
	for(int i=0;i<9;i++) dp[0][i]=1;
	
	for(int i=1;i<n;i++){
		for(int j=0;j<9;j++){
			if(j==0) { 
				if(i==1) dp[i][j]=2;
				else dp[i][j]=((dp[i-2][0]%c)+ (dp[i-1][1]%c))%c;}
			else if(j==8) dp[i][j] = dp[i-1][7]%c;
			else dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%c;
		}
	}
	
	int sum=0;
	for(int i=0;i<9;i++) sum=(sum+dp[n-1][i])%c;
	cout<<sum%c;
	return 0;
}