[동적계획법, 난이도 중] 백준 10844번 쉬운 계단 수

이 문제에서 신경써야 할 조건들이다.

- 인접한 모든 자리수의 차이는 1이어야 한다.

- 0으로 시작할 수 없다.

- 정답을 10억으로 나눈 나머지를 출력해야 한다.

 

아마 이 문제의 정답율이 낮은 이유는 long long 자료형을 모르는 분들이 많아서 그런 것같다.

int는 약 21억을 넘어가면 이상한 값이 나오는데 쓰레기 값이라고 하기도 한다.

이 때 int 대신 범위가 훨씬 더 넓은 long long을 써주면 된다.

 

계산할 때마다 10억으로 나눈다곤 하지만 이런 10개의 변수들을 모조리 합 한다면 21억을 넘을 경우는 충분히 생긴다.

 

아래 표에서 행은 맨오른쪽 끝의 자리수를 의미하며, 열은 숫자의 길이를 의미한다.

즉 DP[i][j] 값은 길이가 j이며 맨마지막에 i라는 자리수가 오는 경우의 수이다.

먼저 길이가 1인 경우부터 살펴보면

이 문제에 주어진 조건으로는 0으로 시작할 수 없기 때문에 1~9까지만 1가지 경우가 가능하다.

길이가 2일 때부터는 끝 자리수가 0 또는 9일 경우, 이전 끝 자리수는 각각 1, 8 밖에 올 수 없다.

그 외의 경우 끝 자리수가 k인 경우(k=1,2,3,...,8) 엔 이전 끝 자리수는 k-1, k+1가 올 수 있으므로

이를 참고하여 DP점화식을 세워주면 되는 것이다.

아래 소스코드를 참고하자.

 

#include <iostream>
using namespace std;
long long n,ans,dp[101][11];
int main()
{
	cin>>n;
	for(int i=1;i<10;i++)dp[1][i]=1;
	for(int i=2;i<=n;i++){
		dp[i][0]=dp[i-1][1];
		for(int j=1;j<10;j++)dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%1000000000;
	}
	for(int i=0;i<10;i++)ans+=dp[n][i];
	cout<<ans%1000000000;
}