문제: https://www.acmicpc.net/problem/17271
알고리즘 분류: 다이나믹 프로그래밍, DP
문제 이해
- N초 동안 스킬을 사용한다
- A 스킬은 1초 소요, B 스킬은 M초 소요
- 빈 시간 없이 스킬을 연속해서 사용해야 한다
- 가능한 모든 스킬 조합의 수를 찾아야 한다
접근 방법: 다이나믹 프로그래밍
dp[i] = "i초까지 가능한 모든 스킬 조합의 수"
i초에서 두 가지 경우의 수:
- 마지막에 A 스킬(1초)을 사용하는 경우:
dp[i-1] - 마지막에 B 스킬(M초)을 사용하는 경우:
dp[i-M]
점화식은,
dp[i] = dp[i-1] + dp[i-M]
내 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
// 다이나믹 프로그래밍 배열 초기화
const dp = Array(N + 1).fill(0);
const MOD = 1000000007;
// 초기값 설정
dp[0] = 1; // 0초일 때는 아무 스킬도 사용하지 않는 한 가지 경우
// 점화식 적용
for (let i = 1; i <= N; i++) {
// A 스킬을 사용하는 경우 (1초 전의 상태에서 가능한 조합 수)
if (i >= 1) {
dp[i] = (dp[i] + dp[i - 1]) % MOD;
}
// B 스킬을 사용하는 경우 (M초 전의 상태에서 가능한 조합 수)
if (i >= M) {
dp[i] = (dp[i] + dp[i - M]) % MOD;
}
}
console.log(dp[N]);