worm/김태진

• 문제 링크
  
• Dynamic Programming
  

//
//  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;
}