본문 바로가기

알고리즘 관련/BOJ

BOJ)11964 Fruit Feast

문제: icpc.me/11964


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)15589 Lifeguards (Silver)  (0) 2018.06.26
BOJ)14965 Lozinke  (0) 2018.06.26
BOJ)11046 팰린드롬??  (0) 2018.06.25
BOJ)1222 홍준 프로그래밍 대회  (0) 2018.06.25
BOJ)15675 괴도 강산  (0) 2018.06.24