N초 동안 가능한 스킬 조합 수 구하기

🧠 TIL - DP로 N초 동안 가능한 스킬 조합 수 구하기

오늘은 스킬의 사용 시간 제약이 있는 조합 문제를 DP로 해결해봤다.
핵심은 dp[i]가 “i초를 채우는 방법의 수”를 의미한다는 점이다.

📌 문제 요약

• 스킬 A: 1초
• 스킬 B: m초
• 총 N초를 정확히 채울 수 있는 모든 조합의 수를 구하라
• 결과는 1,000,000,007로 나눈 나머지 출력

📄 핵심 점화식

dp[i] = dp[i - 1] + dp[i - m]  (단, i ≥ m)

🔍 코드 설명

nanoom = 1_000_000_007
dp = [0] * (n + 1)
dp[0] = 1  # 0초는 아무 것도 안 쓰는 1가지 방법

for i in range(1, n + 1):
    dp[i] += dp[i - 1]  # a 스킬 사용 (1초짜리)
    if i >= m:
        dp[i] += dp[i - m]  # b 스킬 사용 (m초짜리)
    dp[i] %= nanoom  # 오버플로우 방지

print(dp[n])  # N초를 만드는 조합 수

🧪 예시

• n = 3, m = 2
  가능한 조합: aaa, ab, ba → dp[3] = 3
• n = 4, m = 2
  가능한 조합: aaaa, aab, aba, baa, bb → dp[4] = 5

✅ 요약 포인트

• dp[0] = 1은 기저 조건
• dp[i - m]은 반드시 i ≥ m일 때만
• 중간 계산마다 % 1_000_000_007 꼭 해줘야 함
• 문제는 “몇 가지 방법이 있냐”지, 길이나 순서를 묻는 건 아님