[DP] BOJ 2560 짚신벌레

문제 링크 : www.acmicpc.net/problem/2560

2560번: 짚신벌레

문제를 간단하게 생각해야 깔끔하게 점화식을 구할 수 있다.

"dp[k] = k일째 되는 날의 짚신벌레 개체 수"로 두고 문제를 풀어보자.

우선, 예제인 a = 2인 상황에서 짚신벌레가 증식만 한다고 가정한다면 다음과 같다.

0일째 되는 날: (0)

1일째 되는 날: (1)

2일째 되는 날: (2, 0)

3일째 되는 날: (3, 1, 0)

4일 째 되는 날: (4, 2, 1, 0, 0)

5일 째 되는 날: (5, 3, 2, 1, 1, 0, 0)

6일 째 되는 날: (6, 4, 3, 2, 2, 1, 1, 0, 0, 0)

a일째 되는 날부터, 짚신벌레는 a일 전 개체수만큼 증가한다.

따라서, dp[k] = dp[k - 1] + dp[k - a]이다. (단, k >= a)

이는 곧, k - a 일째의 모든 짚신벌레들이 k일째가 됐을 때 성체인 상태임을 의미한다.

이 과정을 잘 기억해두고, 이제는 증식이 멈추는 짚신벌레를 생각해 보자.

 

짚신벌레가 증식을 멈추는 것은 반드시 빨리 생성된 개체부터 늦게 생성된 개체 순으로 일어날 것이다.

따라서, 최초 개체가 증식을 멈추기 시작하는 b일째부터 b일 전 개체수만큼 증식을 멈춘다.

즉 dp[k] = dp[k - 1] + dp[k - a] - dp[k - b]이다. (단, k >= b)

이는 위의 과정과 마찬가지로, k - b일 째의 모든 짚신벌레들이 k일째가 됐을 때 증식을 멈춘 상태라는 것을 의미한다.

 

이처럼 수명이 다해 죽는 짚신벌레의 수도 k - d일 전 개체와 같음을 알 수 있다. (단, k >= d)

이 때, 죽는 짚신벌레의 개체 수는 정답을 구할 때의 마지막에 한 번만 빼주는 것에 유의하자.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
 
int a, b, d, n;
int dp[1000001];
 
void get_dp() {
    for (int i = 0; i < a; i++) dp[i] = 1;
 
    for (int i = a; i <= n; i++) {
        //증식만 진행되는 경우 : 증식되어 증가하는 개체수는 a일 전의 개체 수와 같다.
        dp[i] = (dp[i - 1] + dp[i - a]) % 1000;
        //증식을 멈추기 시작 : 개체의 증가량은 a일 전 개체 수에서 b일 전 개체수를 뺀 만큼이다.
        //즉, 증식을 멈추는 개체 수가 곧 b일 전의 개체수이다.
        if (b <= i) {
            dp[i] = (dp[i] - dp[i - b] + 1000) % 1000;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    cin >> a >> b >> d >> n;
    get_dp();
    int answer = dp[n];
    if (n >= d) answer = (answer + 1000 - dp[n - d]) % 1000;
    printf("%d\n", answer);
 
    return 0;
}

※ mod 연산에 주의