티스토리 뷰

알고리즘 관련/BOJ

BOJ)11964 Fruit Feast

JASON 자손9319 2018. 6. 25. 19:03

문제: 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)11964 Fruit Feast  (0) 2018.06.25
BOJ)11046 팰린드롬??  (0) 2018.06.25
BOJ)1222 홍준 프로그래밍 대회  (0) 2018.06.25
BOJ)15675 괴도 강산  (0) 2018.06.24
댓글
댓글쓰기 폼