dp 백준 쉬운 계단 수 10844

dp 백준 쉬운 계단 수 10844

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

10844번: 쉬운 계단 수

이 문제는 자리수를 입력받아 그 자리수 중 각 수의 차이가 1씩 차이가 나는 수의 개수를 찾는 것이다. 

 

예를들어 

 

1자리수 중에는 아래와같이 9개로 나타낼 수 있다.

1  2  3  4  5  6  7  8  9

 

2자리수 중에는 아래와 같이 17개로 나타낼 수 있다. 

 

10  21  32  43  54  65  76  87  98 

12  23  34  45  56  67  78  89    

 

여기서 공통되는 패턴이 보이는데 앞자리의 +-1의 값이 1씩 차이나는 계단수가 된다. 

그러나 주의할 점이 있다. 끝이 0이거나 9인 수는 -1이나 +1의 경우가 되지 않는다. 위와 같이 98만 되거나 10의 경우 3자리수가 되면 101만 되기 때문에 이 부분을 주의하여 문제를 해결해야한다. 그래서 i==0일때는 +1만 허용하고 i==9는 -1만 을 허용하기 때문에 아래와 같은 점화식을 만들 수 있다. 

if(j != 0 && j != 9)
	arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1];
else if(i == 0)
	arr[i][j] = arr[i-1][j+1];
else if(i == 9)
	arr[i][j] = arr[i-1][j-1];

 

#include <cstdio>

long long arr[103][11];
int main(){
	int N;
	scanf("%d", &N);

	for(int i = 1; i < 10; i++)
		arr[0][i] = 1; 

	for(int i = 1; i <= N; i++){
		arr[i][0] = arr[i-1][1];
		for(int j = 1; j < 10; j++){
			arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1])%1000000000;
		}
	}

	long long result = 0;
	for(int i = 0; i <= 9; i++)
		result += arr[N-1][i] %1000000000;

	printf("%lld", result%1000000000);
}