[BOJ] 11964 : Fruit Feast

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

---

BFS 그래프탐색

[ 문제풀이 ]

 레몬과 오렌지를 먹어서 배부름 정도를 최대로 만들고 싶은데, 이때 물을 중간에 한 번 먹어서 배부름 정도를 절반으로 낮출 수 있다. 레몬과 오렌지의 배부름 정도는 A, B이고 내 최대 배부름은 T이므로 T를 넘지 않는 선에서 레몬과 오렌지를 먹어 만들 수 있는 최대 배부름을 구하자.

 

[ 알고리즘풀이 ]

 ( 배부름 정도, 물을 먹었는지 ) 2개의 값을 가지고 ( 0, 0) 에서 시작해서 BFS 탐색을 진행하면 된다.

 

[ 코드 C++ ]

#include<iostream>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int T, A, B, ans = -1;
    bool visited[500001][2] = {};
 
    cin >> T >> A >> B;
 
    queue<pair<int, bool>> q;
    q.push({ 0, 0 });
    visited[0][0] = 1;
    while (!q.empty()) {
        int curF = q.front().first;
        bool drinkWater = q.front().second;
        q.pop();
 
        ans = max(ans, curF);
 
        if (curF + A <= T && !visited[curF + A][drinkWater]) {
            q.push({ curF + A, drinkWater });
            visited[curF + A][drinkWater] = 1;
        }
        if (curF + B <= T && !visited[curF + B][drinkWater]) {
            q.push({ curF + B, drinkWater });
            visited[curF + B][drinkWater] = 1;
        }
        if (!drinkWater && !visited[curF / 2][!drinkWater]) {
            q.push({ curF / 2, !drinkWater });
            visited[curF / 2][!drinkWater] = 1;
        }
    }
    cout << ans << '\n';
 
    return 0;
}

[ gitHub ]

https://github.com/travelbeeee/BOJ/blob/master/BOJ11964.cpp

travelbeeee/BOJ

---