[Java] 백준 17271번: 리그 오브 레전설 (Small)

🔗 문제

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

 

 

✏️ 풀이

알고리즘 분류: DP

 

난 처음부터 DP라는걸 눈치 채지 못 하고 일단 나이브하게 완탐으로 풀었다. 

DFS라서 `2^N`이나 되기 때문에 시간초과다. 일단 이렇게 해서 답이 나왔다는 걸 알았으니까 이 논리를 가지고 dp로 바꾸면 된다.

import java.io.*;
import java.util.*;
public class Main {

    static int N, M;
    static int answer = 0;
    static Set<String> visited = new HashSet<>();
    static void comb(int sum, String pattern)
    {
        if(visited.contains(pattern)) return;
        visited.add(pattern);

        if(sum > N) return;
        if(sum == N) {
            ++answer;
            return;
        }

        comb(sum + 1, pattern + "A");
        comb(sum + M, pattern + "B");
    }

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

        // 총 N개를 1과 M개로 채우는 경우의 수
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        comb(0, "");
        System.out.print(answer % 1000000007);
    }
}

dp에서 중요한 것은 점화식이다.

dp[i] : i초일때 가능한 조합의 수

• dp[0] : 아무것도 안 고르는 방법이 있다. ⇒ 1
• dp[1] : A 스킬을 사용했다 → 1. 1초전인 (dp[i-1] 을 고대로 가져오면 된다.
• dp[2] : A 스킬을 사용가능하고 i≥M라면 B도 시전할 수 있다. B스킬을 사용하면 M초가 걸리므로 M초전의 값이 필요하다.

즉, if(i ≥ M) dp[i] = dp[i] + dp[i-M] 이라는 점화식을 만들 수 있다.

 

💾  소스

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

public class Main {
    static final int MOD = 1000000007;

    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());

        long[] dp = new long[N + 1];
        dp[0] = 1; // 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]);
    }
}