[99클럽 코테 스터디 15일차] dynamic programming

📌 키워드 

• Dynamic Programming 

📌 문제 요약

• Middler : 리그 오브 레전설 (BOJ,S2) : https://www.acmicpc.net/problem/17271

dp는 아직 감이 없는 것 같다. 이게 완탐, dfs ,, 짱구 굴리다가 아무리 생각해도 시간 내에 안될 것 같아 힌트를 보니 dp.. ㅎㅎ 

그래도 이번 풀이를 통해서 dp에 익숙해지고 있는 것 같다. 

 

N초 동안 게임이 이루어진다. 

1초 동안 A의 스킬을 시전할 수 있고, M초 동안 B의 스킬을 시전할 수 있다. 

N초의 시간 동안, 스킬이 멈추어서는 안된다. 연달아 사용해야 한다는 뜻. 

 

📌  문제 풀이

• dp[i] 정의 : i 초 동안 시전 가능한 스킬의 조합. 
•  i < m : 연속된 A만 사용 가능하다. 따라서 dp[i] = 1 (i < m)
•  i >= m 일때 :  dp[i] = dp[i-1] + dp[i-m] 

A를 덧붙일 수 있는 조합  : dp[i-1] 의 조합. i에서 1초의 시간을 뺀 것이므로 모든 조합의 뒤에 A를 추가할 수 있다. 

B를 덧붙일 수 있는 조합 : dp[i-m] 의 조합. i에서 m초의 시간을 뺀 것이므로 모든 조합의 뒤에 B를 추가할 수 있다. 

 

* 이때  기저조건인 dp[0] = 1 이 된다는 사실도 중요하다. A나 B를 뒤에 붙인다고 생각했을때, 0이 더해지는 것이 아니라 1이 더해져야 한다. 

📌 주의 

dp 계산할 때 마다 mod 를 계산하지 않았더니 계속 틀렸었다. 

점화식이 문제인줄 알았는데 아니었다... 

 

찾아보니 아래 개념을 까먹고 있었다. 

모듈러 연산의 성질 

 

(A + B) % C == ((A % C) + (B % C)) % C

 

dp를 계산할 때 마다 모듈러 연산을 수행하지 않으면, long이라 할지라도 오버플로우가 발생할 수 있다.

 

<코드>

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        // 입력 :  게임 진행 시간 N초, B 스킬 시전 시간 M초
        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]);
        // // A스킬 시전 시간 1초, B스킬 시전 시간 M초 일때, 가능한 스킬 조합의 수를 알고싶다. (스킬을 안쓰고 있는 시간은 없다.)
        // 로직 : dp 점화식 세우기
        // dp[i] i초를 채우는 방법의 수
        // 점화식 dp[0] = 1, dp[1] = 1 , dp[i] = dp[i-1] + dp[i-m]; (i-M >= 0 일때)
        long [] dp = new long[n+1];
        for (int time=0; time<=n; time++){
            if(time < m) dp[time] = 1;
            else {
                dp[time] = dp[time-1] + dp[time-m];
            }
            dp[time] %= 1_000_000_007;
        }
        //A:1초, B:M초 +>   게임 시간 N초일때 가능한 조합의 수
        System.out.println(dp[n]);
    }
}