알고리즘
BOJ 11964 Fruit Feast
굽굿
2022. 4. 16. 20:24
https://www.acmicpc.net/problem/11964
11964번: Fruit Feast
Bessie has broken into Farmer John's house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible. Bessie has a maximum fullness of \(T\) (
www.acmicpc.net
전형적인 DP문제였다.
거스름돈 문제 ( boj 2294) 를 풀었던 사람들은 바로 풀 수 있었을 것이다.
좀더 최적화 할 수 있는 방안은 vector<int> 대신 vector<bool> 을 사용하여 메모리를 줄이는 것이다.
reference site에는 다음과 같이 나와있다.
One potential optimization involves coalescing vector elements such that each element occupies a single bit instead of sizeof(bool) bytes
이를 이용하면 메모리를 많이 아깔 수 있다.
#include <cstdio>
#include <vector>
int T,A,B;
int answer = 1;
std::vector<bool> v;
void dp(){
for(int i=1;i<=T;i++){
if(v[i]) {
if(i+A <= T) v[i+A] = true;
if(i+B <= T) v[i+B] = true;
if(answer < i) answer = i;
}
}
}
int main(){
scanf("%d%d%d",&T,&A,&B);
v.resize(T+1);
v[A] = v[B] = true;
dp();
for(int i=0;i<=T;i++){ if(v[i]) v[i/2] = true; }
dp();
printf("%d\n",answer);
return 0;
}