Worm/김태진 - Revision history

imported>jereneal20 at 09:07, 25 July 2013

2013-07-25T09:07:09Z

← Older revision		Revision as of 09:07, 25 July 2013
Line 72:		Line 72:
	return 0;		return 0;
	}		}
			----
			[[ACM_ICPC/2013년스터디]]

imported>jereneal20 at 09:06, 25 July 2013

2013-07-25T09:06:47Z

← Older revision		Revision as of 09:06, 25 July 2013
Line 2:		Line 2:
	* 문제 [http://211.229.66.5/30stair/worm/worm.php?pname=worm&stair=21 링크]		* 문제 [http://211.229.66.5/30stair/worm/worm.php?pname=worm&stair=21 링크]
	* Dynamic Programming		* 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		// 21_worm.cpp

imported>jereneal20 at 09:00, 25 July 2013

2013-07-25T09:00:05Z

New page

== 짚신벌레/worm ==
* 문제 [http://211.229.66.5/30stair/worm/worm.php?pname=worm&stair=21 링크]
* 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;
}