[10844] 쉬운 계단 수

---

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

10844번: 쉬운 계단 수

 

DP 문제인데 한참을 헤매다가 다른 사람의 풀이를 참고하였다.

 

직접 써내려가면서 규칙을 찾아보려 했으나 

N=4까지만 보고 규칙을 정한 탓에 틀려버렸다.

	for (int i = 3; i <= N; i++) {
		DP[i] = ((DP[i - 1] - (i - 1)) * 2 + (i - 1)) % 1000000000;
	}

아주 엉터리 규칙이었다.

 

 

숫자가 조금 커져도 금방 오차가 커져버렸기 때문에 다시 처음부터 생각하였다.

 

일단 DP 배열을 2차원으로 선언한다.

N-1자리 계단수에서 마지막 수가 0 또는 9이면, N자리 계단수에서 이를 고려하여 경우의 수를 계산해야 한다.

직접 쓰면서 규칙을 찾았다.

i가 0이나 9가 아니면 DP[i-1][j-1]+DP[i-1][j+1]를 하면 된다.(파란색 화살표 참고)

i가 0 또는 9이면 방식이 좀 달라진다.

 

하지만 숫자가 금방 커지기 때문에 오버플로우가 발생한다.

따라서 unsigned long long으로 자료형을 바꾸고 1,000,000,000으로 나눈 나머지를 출력하였다.

 

이를 따른 코드는 아래와 같다.

#include <iostream>
using namespace std;

int N;
unsigned long long DP[101][10];
unsigned long long sum;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	/* 초기값 설정 */
	for (int i = 0; i <= 9; i++) {
		if (i == 0)DP[1][i] = 0;
		else DP[1][i] = 1;
	}

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) DP[i][j] = DP[i - 1][j + 1] % 1000000000;
			else if (j == 9) DP[i][j] = DP[i - 1][j - 1] % 1000000000;
			else DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % 1000000000;
		}
	}

	for (int i = 0; i <= 9; i++) {
		sum += (DP[N][i]);
	}
	cout << sum % 1000000000;

}