[BAE/<JOON> 문제풀이] 2560. 짚신벌레

https://www.acmicpc.net/problem/2560

2560번: 짚신벌레

서론

추석이라 고향가서 풀었는데 옆에 아시안 게임 틀어놓으니까 진짜 집중이 안된다.

DP는 문제푸는 시간 길어지면 뭔가 스스로 생가깅 꼬이는 느낌이다.

풀이

벌레 상태 ( 유충, 가임, 불임 ) 에 따라 구분해서 풀이를 작성한다.

여기서 가임과 불임 판정은 그 벌레가 태어난 일자를 기준으로 할 것이므로 날마다 태어난 유충 수는 별도로 저장했다.

 

오늘 태어난 유충 수 : 어제 가임 유충 수 + 오늘-a 날 태어난 유충 수 ( 가임으로 바뀌는 즉시 번식함 ) - 오늘-b날 태어난 유충수 ( 불임으로 바뀌는 날 번식 못함 )

가임 유충 수 : 어제 가임 유충 수 + 오늘-a 날 태어난 유충 수 - 오늘-b날 태어난 유충 수

불임 유충 수 : 어제 불임 유충 수 + 오늘-b 날 태어난 유충 수 - 오늘-d날 태어난 유충 수 ( 사망 )

 

위의 점화식으로 계산하고 다 더하면 오늘 살아있는 벌레 수가 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 1000;
int main() {
    int a, b, d, n; cin >> a >> b >> d >> n;
    vector<int> dp(n + 1); vector<vector<int>> arr(n + 1, vector<int>(3));
    arr[0][0] = 1;
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        arr[i] = arr[i - 1];
        dp[i] = arr[i][1];
        arr[i][0] += arr[i][1];
        if (i >= a) {            
            arr[i][1] += dp[i - a];
            dp[i] += dp[i - a];
        }
        if (i >= b) {
            arr[i][0] -= dp[i - b];
            arr[i][1] -= dp[i - b];            
            arr[i][2] += dp[i - b];
            dp[i] -= dp[i - b];
        }
        if (i >= d) {
            arr[i][2] -= dp[i - d];            
        }
        dp[i] += mod; dp[i] %= mod;
        arr[i][0] += mod; arr[i][1] += mod; arr[i][2] += mod;
        arr[i][0] %= mod; arr[i][1] %= mod; arr[i][2] %= mod;
        //cout << arr[i][0] << " " << arr[i][1] << " " << arr[i][2] << "\n";
    }
    cout << (arr[n][0] + arr[n][1] + arr[n][2]) % mod;
    return 0;
}