Link
https://www.acmicpc.net/problem/2560
Detail
이 문제는 언뜻 보았을 때, 시뮬레이션 말고는 다른 답이 없어보인다. 하지만 문제를 잘 읽어보면 깔끔하게 구할 수 있는 값이 하나 있다.
바로 n일차에 “태어난” 벌레의 수를 구할 수 있다. 이 값을 정확하게 저장하고 알 수있다면, (n - 1)일차에 어떤 벌레들이 성장중인지, 재생산중인지, 생산을 멈추고 죽는날만을 기다리는지 모두 구할 수 있다.
그렇게 바로 sigma 함수를 만들어서 문제를 들어갔는데, 시간초과에 걸렸다.
그래서 모든 dp배열을 sigma로 구한다는 점에서 착안하여, 이 문제가 누적합 문제의 해법까지 적용해서 완전히 풀 수 있는 문제임을 알게 되었다.
우선, 이 문제는 0일차에서 시작해서 target일차까지의 진행을 표기하는데, 누적합 문제에서는 1부터 시작하는 것이 깔끔하기 때문에 target일차를 1 늘리고 진행했다.
dp 배열의 구성은 다음과 같다.
- i : 1일차부터 target일차까지 태어난 벌레들의 누적합
Code
#include <bits/stdc++.h>
using namespace std;
inline int mod(int a) {
if(a < 0) a += 10000;
return a % 1000;
}
inline int clamp(int a) {
return max(0, a);
}
int main()
{
int adult_day;
int end_prod_day;
int die_day;
int target_day;
cin >> adult_day >> end_prod_day >> die_day >> target_day;
// 누적합은 0번 index 비우고 1번 index부터 시작해야 깔끔
// 0일차부터 target_day일차까지의 벌레 수를 구해야함
// 1일차에서 시작한다고 보고 target_day 1증가
target_day++;
// 기간 1 : 성체가 되고있는 과정의 벌레 수 = 이전 기간 재생산중인 벌레 수를 적당히 더하면 됨
// 기간 2 : 성체가 된 후 재생산중인 벌레 수 = 자라서 성체가 된 놈들
// 기간 3 : 재생산을 멈춘 벌레들
// dp[0][cur_time] = sigma(cur_time - adult_day + 1, cur_time, dp[1]);
// dp[1][cur_time] = sigma(cur_time - end_prod_day + 1, cur_time - adult_day, dp[1])
// dp[2][cur_time] = sigma(cur_time - die_day + 1, cur_time - end_prod_day, dp[1]);
// sigma로 통일되어있는거보니 누적합으로 구할 수 있어보이는데
// dp[i] = 당일 생산 된 벌레 수의 누적 합
vector dp(target_day + 1, 0);
dp[0] = 0;
dp[1] = 1; // 1일차에 임의로 벌레 추가
// cout << 1 << ' ';
for(int cur_time = 2; cur_time <= target_day; cur_time++)
{
int start = clamp(cur_time - end_prod_day);
int end = clamp(cur_time - adult_day);
int created_today = mod(dp[end] - dp[start]);
dp[cur_time] = mod(dp[cur_time - 1] + created_today);
// cout << created_today << " ";
}
// cout << endl;
// print
// for(int i = 1; i <= target_day; i++) {
// cout << dp[i] << " ";
// } cout << endl;
int all = mod(dp[target_day] - dp[clamp(target_day - die_day)]);
cout << all << endl;
}