BOJ 17271 - 리그 오브 레전설 (Small) 링크
(2024.03.28 기준 S2)

문제

A 스킬의 시전 시간은 $1$초, B 스킬의 시전 시간은 $M$초이다. 시전 시간 동안은 다른 스킬을 사용할 수 없으며 스킬을 쓰지 않는 시간은 없어야 할 때, $N$초 동안 가능한 스킬 조합의 수 출력

알고리즘

간단한 DP

풀이

$i$초 때 가능한 경우의 수는 두 가지가 있다.
1. $i-1$초까지 스킬 쓴 상태에서 A 스킬 사용
2. $i \ge M$일 때, $i-M$초까지 스킬 쓴 상태에서 B 스킬 사용

결국 다음과 같은 점화식을 도출할 수 있다.
$dp(i) = dp(i-1) + dp(i-M)$

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1'000'000'007;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;

    // i초 때 가능한 경우의 수는 두 가지가 있다.
    // i-1초까지 스킬 쓴 상태에서 A 스킬 사용
    // i >= M일 때, i-M초까지 스킬 쓴 상태에서 B 스킬 사용
    // dp(i) = dp(i-1) + dp(i-M)

    int dp[N + 1]; fill(dp, dp + N + 1, 1);
    for (int i = M; i <= N; i++) // M초 미만일 땐 dp[i] = dp[i-1]이기 때문에 무조건 1이다.
        dp[i] = (dp[i - 1] + dp[i - M]) % MOD;

    cout << dp[N];
}

• Python

import sys; input = sys.stdin.readline
MOD = 1000000007

N, M = map(int, input().split())

# i초 때 가능한 경우의 수는 두 가지가 있다.
# i-1초까지 스킬 쓴 상태에서 A 스킬 사용
# i >= M일 때, i-M초까지 스킬 쓴 상태에서 B 스킬 사용
# dp(i) = dp(i-1) + dp(i-M)

dp = [1] * (N + 1)
for i in range(M, N + 1): # M초 미만일 땐 dp[i] = dp[i-1]이기 때문에 무조건 1이다.
    dp[i] = (dp[i - 1] + dp[i - M]) % MOD

print(dp[N])