BOJ 11964 Fruit Feast

https://www.acmicpc.net/problem/11964

11964번: Fruit Feast

 

전형적인 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;
}

 

참고
https://en.cppreference.com/w/cpp/container/vector_bool