99클럽 코테 스터디 15일차 TIL - 리그 오브 레전설 (Small) (dp)

문제: https://www.acmicpc.net/problem/17271

접근 방식

• dp[i]는 i초 동안 가능한 스킬 조합의 수를 저장
  • 처음에는 dp[0] = 1로 설정 (0초 동안 아무것도 하지 않는 방법은 1가지)
• 점화식
  • dp[i] = dp[i-1] + dp[i-m] (단, i-m >= 0일 때만)
    • dp[i-1]은 1초 동안 A 스킬을 사용한 경우이고 dp[i-m]은 m초 동안 B 스킬을 사용한 경우
• 모듈러 연산: 가능한 값이 너무 커질 수 있으므로, 결과는 항상 1,000,000,007로 나누어야 함

구현

const fs = require("fs");
const [n, m] = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map(Number);

const MOD = 1000000007;
const dp = new Array(n + 1).fill(0);
dp[0] = 1; // 0초 동안 할 수 있는 방법은 1가지 (아무것도 하지 않음)

for (let i = 1; i <= n; i++) {
  dp[i] = (dp[i] + dp[i - 1]) % MOD; // A 스킬 사용

  if (i >= m) {
    dp[i] = (dp[i] + dp[i - m]) % MOD; // B 스킬 사용
  }
}

console.log(dp[n]); // n초 동안 가능한 스킬 조합의 수 출력