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

✅ 오늘의 학습 키워드

• 다이나믹 프로그래밍(DP)
• 기저 상태(Base case)
• 모듈러 연산(mod)

---

✅ 공부한 내용

✔️ 문제 요약

(백준 문제 링크: https://www.acmicpc.net/problem/17271)

이 문제는 게임에서 두 가지 스킬(A와 B)을 사용하여 N초 동안 싸움을 할 때, 가능한 모든 스킬 조합의 수를 구하는 문제입니다.

• A 스킬: 시전 시간 1초
• B 스킬: 시전 시간 M초
• 규칙: 스킬 시전 중에는 다른 스킬을 사용할 수 없고, 스킬을 사용하지 않는 시간이 없어야 함

결과는 아주 큰 수가 될 수 있으니 1,000,000,007로 나눈 나머지를 출력해야 한다.

✔️ 풀이 로직

이 문제는 전형적인 다이나믹 프로그래밍(DP) 문제다. (물론 기저 상태 설정 안해서 못푼...바보..)
각 시간에서 가능한 모든 경우의 수를 이전 상태에서의 결과를 활용해 구해나가는 방식으로 풀었다.

 

1. DP 테이블 정의: dp[i]를 '정확히 i초를 채우는 방법의 수'라고 정의했다. 최종 목표는 dp[N]을 구하는 것!!

 

2. 기저 상태 설정:

dp[0] = 1;

- 0초를 채우는 방법은 아무것도 안 하는 1가지 경우뿐이다. 이게 모든 계산의 시작점이다. -> 이거 빼먹으면 틀린다!

 

3. 점화식 도출: i초를 채우기 위한 마지막 스킬이 무엇이었을까? 두 가지 경우로 나눌 수 있다.

• 마지막 스킬이 A(1초)일 경우: 그전까지 i-1초를 채웠어야 한다. 방법의 수는 dp[i-1]가지.

long long a = dp[i-1];  // `i-1`초 상태에서 A스킬(1초)을 사용하는 경우의 수

• 마지막 스킬이 B(M초)일 경우: 그전까지 i-M초를 채웠어야 한다. 방법의 수는 dp[i-M]가지.
  (단, 이 경우는 i가 M보다 크거나 같을 때만 가능하다.)

long long b = 0;        // B 스킬을 사용하는 경우의 수 (초기값 0)

if(i >= m){             // i가 B 스킬 시전 시간 이상일 때만 B 스킬 사용 가능
    b = dp[i-m];        // i-M초 상태에서 B스킬(M초)을 사용하는 경우의 수
}

• 따라서, dp[i] = dp[i-1] + dp[i-M] (단, i >= M일 때만 dp[i-M]을 더한다) 라는 점화식을 세울 수 있다.

4. DP 테이블 채우기: i를 1부터 N까지 증가시키면서 위 점화식을 이용해 dp 배열을 순서대로 채워나간다.

 

5. 모듈러 연산: 덧셈을 할 때마다 결과가 너무 커지지 않도록 1,000,000,007로 나눈 나머지를 dp[i]에 저장한다. -> 이거 빼먹으면 틀린다! 문제를 잘 읽자!

dp[i] = (a + b) % mod;  // 두 경우의 수를 더하고 모듈러 연산 수행

 

6. 결과: 최종적으로 dp[N]에 저장된 값을 출력.

코드 진행 과정 (N=4, M=2 예시)

1. 초기화:
   • dp[0] = 1 (기저 상태, 계산의 시작점)
2. dp[1] 계산:
   • A 스킬만 사용 가능 (B 스킬은 2초 필요)
   • dp[1] = dp[0] = 1 (A 한 번 사용)
3. dp[2] 계산:
   • A 스킬 경우: dp[1] = 1 (1초 상태에서 A 추가)
   • B 스킬 경우: dp[0] = 1 (0초 상태에서 B 추가)
   • dp[2] = 1 + 1 = 2 (AA, B)
4. dp[3] 계산:
   • A 스킬 경우: dp[2] = 2 (2초 상태에서 A 추가)
   • B 스킬 경우: dp[1] = 1 (1초 상태에서 B 추가)
   • dp[3] = 2 + 1 = 3 (AAA, BA, AB)
5. dp[4] 계산:
   • A 스킬 경우: dp[3] = 3 (3초 상태에서 A 추가)
   • B 스킬 경우: dp[2] = 2 (2초 상태에서 B 추가)
   • dp[4] = 3 + 2 = 5 (AAAA, BAA, ABA, AAB, BB)

---

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떻게 해결을 했는지

DP 테이블 dp[i]를 'i초를 채우는 방법의 수'로 정의하는 것까진 좋았는데, 점화식을 세우는 게 조금 헷갈렸다. dp[i]를 이전 값들로 어떻게 표현할지 고민하다가, 마지막이 A스킬(1초)이었는지, B스킬(M초)이었는지로 생각하니 dp[i-1]과 dp[i-M]을 더하면 된다는 결론에 도달했다.

- 🤩 무엇을 새롭게 알았는지

• DP 문제의 기본적인 접근 방식, '상태 정의 -> 기저 상태 설정 -> 점화식 도출 -> 테이블 채우기' 의 흐름을 다시 한번 연습할 수 있었다.
• DP에서 기저 상태(base case) 설정의 중요성을 다시 느꼈다.

---

✅ 전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main(){
    cin.tie(NULL), cout.tie(NULL);
    ios::sync_with_stdio(false);

    int n, m; // 목표 시간 N, 시전 시간 M
    cin >> n >> m;

    long long mod = 1000000007; // 문제에서 요구하는 나머지 연산의 모듈러 값

    // DP 배열 생성, dp[i] = i초 동안 가능한 스킬 조합의 수
    vector<long long> dp(n+1, 0); //  크기는 N+1로 하여 인덱스 0부터 N까지 사용.

    // 기저 상태(Base Case) 설정
    dp[0] = 1;  // 0초 -> 아무 스킬도 사용하지 않는 1가지 경우

    // dp 점화식 생성
    // i = 1초부터 N초까지 순서대로 계산
    for (int i = 1; i <= n; i++){
        long long a = dp[i-1];  // i-1초 상태에서 A스킬(1초)을 사용하는 경우의 수
        long long b = 0;        // B 스킬을 사용하는 경우의 수 (초기값 0)

        if(i >= m){             // i가 B 스킬 시전 시간 이상일 때만 B 스킬 사용 가능
            b = dp[i-m];        // i-M초 상태에서 B스킬(M초)을 사용하는 경우의 수
        }

        dp[i] = (a + b) % mod;  // 두 경우의 수를 더하고 모듈러 연산 수행
    }

    cout << dp[n] << '\n';

    return 0;
}