99클럽 코테 스터디 15일차 TIL - 리그 오브 레전설(Small) 백준 17271번

오늘의 학습 키워드

• DP
• 점화식
• 최적화

---

공부한 내용 정리

문제는 N초 동안 A(1초) 또는 B(M초) 스킬을 사용해 시간을 정확히 채우는 방법의 수를 구하는 것이었습니다.
이때 모듈러 연산(1,000,000,007로 나눈 나머지)을 적용해 결과를 출력해야 했습니다.

핵심 아이디어는 다음과 같습니다:

• dp[i] = i초를 만드는 방법의 수
• dp[i] = dp[i-1] + dp[i-M]
  • dp[i-1]: 1초짜리 스킬(A)을 하나 추가한 경우
  • dp[i-M]: M초짜리 스킬(B)을 하나 추가한 경우 (단, i ≥ M일 때만)
• 초기 상태로 dp[0] = 1 (0초를 만드는 방법은 아무것도 사용하지 않는 방법 1개)

작은 문제부터 차근차근 쌓아나가면서 최종적으로 dp[N] 값을 구했습니다.

---

소스코드

/*
백준 17271
입력: N M
조건: A시간 1 ~ 10000
    A의 시전시간은 1초
    B의 시전시간 2초
    B시간 M초 2~100
    dp[0] = 0초를 만들 수 있는 방법의 수 : 1
    dp[1] = 1초를 만들 수 있는 방법의 수 : 1초짜리 추가
    dp[1] = dp[0] + dp[1]
    dp[2] = 2초를 만들 수 있는 방법의 수 : M초 짜리 추가 불가능하면 1초짜리 추가
    dp[2] = dp[1] + dp[1]
    i초를 만드는 방법:
        i-1초를 만들고 거기에 1초짜리 A스킬 몇개 추가
        i-M초 만들고 거기에 M초짜리 B추가
        M초 보다 작으면 1초짜리로 추가 
        dp[i] = dp[i-1]
        근데 M초보다 크다? 그럼 M초 짜리도 더해줘야함
        dp[i] = dp[i] + dp[i-M]
        결과는 이 두개를 더함.
출력: N초 내에 가능한 모든 AB의 조합
*/
import java.io.*;
import java.util.*;

public class Main {
    static int MOD = 1_000_000_007;
    public static void main(String[] args) throws IOException {
        // --- 입력 ---
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();

        StringTokenizer st = new StringTokenizer(line);
        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]; // 1초짜리 추가
            if (i - M >= 0) {
                dp[i] = (dp[i] + dp[i - M]) % MOD; // M초짜리 추가
            }
        }

        System.out.println(dp[N]);
    }
}

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 단순한 경우의 수 문제라고 생각했지만, "어떤 순서로든 스킬을 사용해 시간을 채운다"는 부분에서 중복을 고려해 순서를 다르게 만들 수 있다는 점을 주의해야 했습니다.

 

• 어떻게 해결했는지

점화식 dp[i] = dp[i-1] + dp[i-M]을 세워 이전 상태로부터 현재 상태를 만드는 방식으로 동적 계획법을 적용했습니다.
또한, 계산 중간마다 모듈러 연산을 적용해 오버플로우를 방지했습니다.

 

 

 

• 무엇을 새롭게 알았는지

"몇 초를 만드는 방법"처럼 순서가 중요한 조합 문제는 DP로 푸는 것이 적절하다는 것

그리고, N이 10,000처럼 꽤 클 때는 매 반복마다 % MOD 처리를 해줘야 한다는 점.

 

 

 

• 내일 학습할 것은 무엇인지

DP문제가 많이 어려워서 다양한 유형의 문제를 풀어보고 점화식을 빠르게 도출해 내는 것이 중요한 것 같아서. 여러 문제를 풀어봐야겠습니다.

---