BOJ 10844: 쉬운 계단 수

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

---

알고리즘 분류 | 동적 계획법 (Dynamic Programming, DP)

풀이 |

문제에서 길이가 N인 계단 수가 총 몇 개인지 구하라고 했기 때문에 dp[n]에 들어갈 값은 길이가 n인 계단 수의 개수다.

다만 여기서는 dp[n][l]으로 하여 n번째 숫자가 무엇인지 확인하여 +1 혹은 -1을 해주어야 한다.
즉, 길이가 n이면서 n번째 수(l)가 1 ~ 8 이라면 n-1번째 수는 l+1 혹은 l-1로 생각할 수 있다.
그러므로 1 <= l <= 8이면 dp[n][l] = dp[n-1][l+1] + dp[n-1][l-1]

하지만 l이 0이면 -1 할 수 없기 때문에 dp[n][l] = dp[n-1][1]
마찬가지로 9는 +1 할 수 없기 때문에 dp[n][l] = dp[n-1][8]

정답을 1,000,000,000로 나누어주라고 했는데 출력하기 직전에만 나누어주니 틀렸다고 나왔다.

틈틈히 dp배열을 업그레이드 할 때마다 나누어줘야 한다.

소스 코드 |

#include <iostream>
using namespace std;
long long dp[101][10];
#define mod 1000000000

int main(void) {
	ios_base::sync_with_stdio(false);
	int num;
	long long ans = 0;
	cin >> num;

	for (int i = 1; i < 10; i++) {
		dp[1][i] = 1;
	}

	for (int i = 2; i <= num; i++) {
		dp[i][0] = dp[i - 1][1];
		dp[i][9] = dp[i - 1][8];
		for (int j = 1; j <= 8; j++) {
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
		}
	}

	for (int i = 0; i < 10; i++) {
		ans += dp[num][i];
	}
	cout << ans % mod << '\n';

	return 0;
}