- 문제 링크
- Dynamic Programming
- 벌레는 태어난지 a날부터 b날까지 매일 한마리의 벌레를 낳고 태어난지 d날째에 죽는다. N날이 지났을 때 벌레는 몇마리?
- 점화식 사용
- N일의 개체수 = N-1일의 개체수(태어난 것 불포함) + N일에 태어난 수 - N-d일 태어난 수(오늘 죽는 수)
- N일 태어난 수 = N일 출산 가능한 수 = N-1일 출산가능 + N일 성체가되는 수 - N일 출산불가시작개체 수
- = N-1일 출산가능 + N-a일 태어난 수 - N-b일 태어난 수
- 주의
- N일 태어난 수가 N일 출산 가능 수와 항상 같은가? -> 0번째날은 아님
//
// 21_worm.cpp
// dovelet
//
// Created by Jereneal Kim on 13. 7. 25..
// Copyright (c) 2013년 Jereneal Kim. All rights reserved.
//
#include <stdio.h>
#include <iostream>
using namespace std;
int arr[1000001]={0}; // n째 개체수
int arr2[1000001]={0}; // n째 출산가능수,태어난수
int main()
{
int a,b,d,N,i;
scanf("%d %d %d %d",&a,&b,&d,&N);
arr2[0]=arr[0]=1;
if(a==1){
arr[1]=arr[0]+1;
arr2[1]=1;
}else{
arr[1]=arr[0];
}
for(i=2;i<=N;i++){
if(i>=a){
if(i>=b){
arr2[i]=arr2[i-1]+arr2[i-a]-arr2[i-b];
}else{
arr2[i]=arr2[i-1]+arr2[i-a];
}
if(i>=d){
arr[i]=arr[i-1]+arr2[i]-arr2[i-d];
}else{
arr[i]=arr[i-1]+arr2[i];
}
}else{
arr2[i]=arr2[i-1];
arr[i]=arr[i-1];
}
if(arr[i]<0){
arr[i]+=1000;
}
if(arr2[i]<0){
arr2[i]+=1000;
}
arr[i]%=1000;
arr2[i]%=1000;
}
printf("%d",arr[N]%1000);
return 0;
}