[Algorithm] 리그 오브 레전설

Jong Min ·2025년 4월 18일

algorithm

Algorithm

목록 보기

16/30

백준 17271번 – 리그 오브 레전설 (Small)

🔗 리그오브 레전설

📌 문제 설명

규환이는 리그 오브 레전설이라는 게임을 좋아한다.
이 게임에서는 N초의 시간 동안 싸움을 하는데, 규환이가 플레이하는 캐릭터는 A, B 두 가지 스킬을 사용할 수 있다.

A 스킬의 시전 시간은 1초
B 스킬의 시전 시간은 M초

규환이는 다양한 스킬 조합을 원하기 때문에, 가능한 모든 스킬 조합의 개수를 알고 싶어 한다.
단, 스킬을 시전하는 동안에는 다른 스킬을 사용할 수 없으며, 빈 시간 없이 총 시간이 딱 N초가 되어야 한다.

예를 들어, N = 4, M = 2이면 가능한 스킬 조합은

AAAA, AAB, ABA, BAA, BB

총 5가지이다.

입력 & 출력

입력
첫 번째 줄에 두 정수 N, M이 주어진다.
- N: 싸움 시간(1 ≤ N ≤ 10,000)
- M: B 스킬 시전 시간(2 ≤ M ≤ 100)
출력
가능한 스킬 조합의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

✨ 예제 입력 1

4 2

✨ 예제 출력 1

💡 문제 핵심

순서가 다른 조합은 모두 다른 스킬 조합으로 본다.
N초를 정확히 채우기 위해 A(1초)와 B(M초)를 조합하는 경우의 수를 구해야 한다.
결과가 매우 커질 수 있으므로 MOD 연산을 적용한다.

🔍 풀이 아이디어 (DP)

DP 정의
dp[i] = 총 시간이 i초일 때 가능한 스킬 조합의 수 (MOD 적용)
초기값
- dp[0] = 1 (아무 스킬도 쓰지 않은 상태 하나)
점화식
- 모든 경우는 마지막에 A를 사용한 경우와 마지막에 B를 사용한 경우로 나눌 수 있다.
- A 사용: dp[i-1]
- B 사용: i >= M인 경우에만 dp[i-M]
```
dp[i] = dp[i-1];
if (i >= M) {
    dp[i] = (dp[i] + dp[i-M]) % MOD;
}
```

✅ 자바 코드

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] dp = new int[N+1];
        dp[0] = 1;
        for (int i = 1; i <= N; i++) {
            dp[i] = dp[i-1];  // 마지막에 A 스킬
            if (i >= M) {
                dp[i] = (dp[i] + dp[i-M]) % MOD;  // 마지막에 B 스킬
            }
        }
        System.out.println(dp[N]);
    }
}