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

문제 출처 - Baekjoon Online Judge

문제는 여기

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. 값들을 입력받아준다.

2. dp[0]을 1로 초기화해준다.

3. dp[i]를 1초마다 사용할 수 있는 기술이 있으므로 이전 값을 초기값으로 잡아준다.

4. b보다 값이 크다면 b초마다 사용할 수 있는 기술을 사용할 수 있으므로 b초 전에 dp값을 dp[i]에 더해준다.

5. 4에서 나온 값을 mod 값으로 나눠준다.

6. 결과를 출력한다.

[접근]

1. DP문제로 1초의 경우와 B초의 경우를 구하면 되겠다고 생각하였다.

[코드]

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

public class Main {
	static int n, b;
	static int[] dp;
	static int mod = 1000000007;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		
		dp = new int[100001];
		
		dp[0] = 1;
		for (int i = 1; i <= n; i++) {
			// 1초쿨 기술
			dp[i] = dp[i - 1];
			
			// b초쿨 기술
			if (i >= b)
				dp[i] += dp[i - b];
			
			dp[i] %= mod;
		}
		
		System.out.println(dp[n]);
	}

}