Difference between r1.1 and the current
@@ -1,6 +1,15 @@
== 짚신벌레/worm ==
* 문제 [http://211.229.66.5/30stair/worm/worm.php?pname=worm&stair=21 링크]
* Dynamic Programming
{{{
//
// 21_worm.cpp
* 문제 [http://211.229.66.5/30stair/worm/worm.php?pname=worm&stair=21 링크]
* 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
@@ -64,3 +73,5 @@
return 0;
}
}}}
}
}}}
----
[ACM_ICPC/2013년스터디]
짚신벌레/worm ¶
- 문제 링크
- 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-1일 출산가능 + N-a일 태어난 수 - N-b일 태어난 수
- N일의 개체수 = N-1일의 개체수(태어난 것 불포함) + N일에 태어난 수 - N-d일 태어난 수(오늘 죽는 수)
- 주의
- N일 태어난 수가 N일 출산 가능 수와 항상 같은가? -> 0번째날은 아님
- 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; }