[백준]#17271 리그 오브 레전설 (Small)

문제

규환이는 리그 오브 레전설이라는 게임을 좋아한다. 이 게임에서는 N초의 시간 동안 싸움을 하는데, 규환이가 플레이하는 캐릭터는 A, B 두 가지 스킬을 사용할 수 있다. A 스킬의 시전 시간은 1초고, B 스킬의 시전 시간은 M초이다. 규환이는 다양한 스킬 조합을 원하기 때문에 가능한 모든 스킬 조합을 알아보고 싶어 한다. 단, 시전 시간 동안은 다른 스킬을 사용할 수 없으며, 스킬을 안 쓰고 있는 시간은 없어야 한다.

예를 들어, N이 4초이고, M이 2초이면 가능한 스킬 조합은 AAAA, AAB, ABA, BAA, BB로 5가지가 가능하다.

입력

첫 번째 줄에 싸움 시간 N과 B 스킬의 시전 시간 M이 주어진다. (N은 10,000 이하의 자연수, M은 2 이상 100 이하의 자연수)

출력

가능한 조합의 수를 1,000,000,007로 나눈 나머지 값을 출력한다.

예제 입력 1

4 2

예제 출력 1

5

예제 입력 2

3 2

예제 출력 2

3

풀이

이 문제는 점화식을 구해서 DP 알고리즘을 이용해 풀 수 있었다.

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Main {
    static int[][] dp = new int[10001][5001];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        int ans = 0;

        for(int i=0; i<=N/M; i++) {
            ans += dfs(N-(i*M), i);
            ans %= 1000000007;
        }

        System.out.println(ans);
    }

    public static int dfs(int x, int y) {
        if(x==0 && y==0)
            return dp[x][y] = 0;

        else if(x==0 || y==0)
            return dp[x][y] = 1;

        if(dp[x][y]==0)
            dp[x][y] = ((dfs(x, y-1))%1000000007 + (dfs(x-1, y))%1000000007) % 1000000007;

        return dp[x][y];
    }
}