[주의][다이나믹 프로그래밍] 쉬운 계단 수

문제 링크 : https://www.acmicpc.net/problem/10844

쉬운 계단 수 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 24847 7522 5520 28.535% 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1  1 예제 출력 1  9 예제 입력 2  2 예제 출력 2  17

[ 문제 풀이 ]

- D[i][j] = 마지막 수가 i로 끝나는, j자리 계단수의 개수

ex) D[1][2] = 마지막이 1로 끝나는 2자리 계단수의 개수

문제에서 0으로 시작하는 자리는 없다고 하였으므로, 

D[0][1]은 0으로 놓고, D[1~9][1]은 1로 놓고 다음과 같이 생각 할 수 있다.

ex 1) D[9][2]는 마지막이 9로 끝나는 두자리 계단수. 89 = 1가지 경우밖에 없다.

ex 2) D[2][2]는 마지막이 2로 끝나는 두자리 계단수. 12, 32 = 2가지 경우가 있다.

ex 3) D[0][2]는 마지막이 0으로 끝나는 두자리 계단수. 10 = 1가지 경우밖에 없다.

즉, D[i][j] = D[i - 1][j - 1] + D[i + 1][j - 1]  (i는 마지막수, j는 자리수)

[ 주의 사항 ]

- 문제 출력 조건에서 정답을 10억으로 나눈 값을 출력하라고 명시되어있다. 참고로 32bit에서 int의 최대값은 약 21억이다.

- 굳이 long long으로 처리할 필요없이 int 범위에서도 충분히 처리할 수 있다. 그러나 + 연산하는 과정에서 오버플로우가 발생할 위험이 있으므로 + 연산 할 때마다 나머지를 취해준다.

if (i - 1 >= 0) D[i][j] = (((long long)D[i][j]) + D[i - 1][j - 1]) % 1000000000;   // 먼저 long long으로 바꾸고 더해야 안잘린다.

- 마지막 결과 변수(result)는 배열이 아닌 1개 이므로 그냥 편하게 long long으로 선언했다.

---

[ 최종 구현(C++) ]

#include <stdio.h>
#define MAX_NUMBER_SIZE 102

int D[10][MAX_NUMBER_SIZE] = { 0 };

int main(void)
{
	int N;
	long long result = 0;

	scanf("%d", &N);

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

	for (register int j = 2; j <= N; j++)
	{
		for (register int i = 0; i < 10; i++)
		{
			if (i - 1 >= 0) D[i][j] = (((long long)D[i][j]) + D[i - 1][j - 1]) % 1000000000;
			if (i + 1 <= 9) D[i][j] = (((long long)D[i][j]) + D[i + 1][j - 1]) % 1000000000;
		}
	}

	for (register int i = 0; i < 10; i++)
	{
		result = (result + D[i][N]) % 1000000000LL;
	}

	printf("%lld\n", result);

	return 0;
}