BOJ)11964 Fruit Feast

문제: icpc.me/11964

최대 포만감의 최대치가 t이고, 오렌지를 먹으면 a만큼 레몬을 먹으면 b만큼 포만감이 오를 때, 최대 포만감을 구하는 문제이다.

단, 조건이 하나 있는데 딱 한번 물을 마시면 현재 포만감을 반으로 줄일 수 있다.

현재 물을 마셨는 지 아닌지를 제약조건으로 둔다면 다이나믹 프로그래밍으로 문제를 해결할 수 있다.

dp[i][j]= 포만감이 i이고 제약조건(물을 마셨는 지 여부)이 j일 때 상태의 존재 여부

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[5000005][2];
int t,a,b,r;
int main(){
    scanf("%d%d%d",&t,&a,&b);
    dp[a][0]=1,dp[b][0]=1;
    dp[a/2][1]=1,dp[b/2][1]=1;
    for(int i=1;i<=t;i++){
        if(i-a>0)dp[i][0]|=dp[i-a][0];
        if(i-b>0)dp[i][0]|=dp[i-b][0];
        dp[i/2][1]|=dp[i][0];
        dp[i][1]|=dp[i][0];
    }
    for(int i=1;i<=t;i++){
        if(i-a>0)dp[i][1]|=dp[i-a][1];
        if(i-b>0)dp[i][1]|=dp[i-b][1];
    }
    for(int i=1;i<=t;i++)
        if(dp[i][1])r=i;
    printf("%d\n",r);
    return 0;
}