[백준] 11964 Fruit Feast

최대값이 T이고 +A,+B가 가능하다

추가로 한번 /2를 할 수 있다

이때 얻을 수 있는 최대값을 구하는 문제다

나누기는 내가 가질 수 있는 최대값에서 나누는게 최적이다

그래서 pq를 이용해서 문제를 풀면 된다

pq에 {(나누기 가능여부, 값)}를 넣고 쭉 돌려보면된다!

이때 진짜 +A,+B를 하면 시간초과가 나니까

A,B를 넣을 수 있는만큼 최대로 넣고 돌면된다!

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
int t, a, b,ans;
bool check[5000050][2];
int main() {
    scanf(" %d %d %d", &t, &a, &b);
    priority_queue<pair<int, int>> pq;
    pq.push({ 1,a });
    pq.push({ 1,b });
    while (!pq.empty()) {
        int cnt = pq.top().first;
        int pos = pq.top().second;
        pq.pop();
        if (pos > t) continue;
        check[pos][cnt] = true;
        ans = max(ans, pos);
        if (cnt && !check[pos/2][0]) pq.push({ 0,pos / 2 });
        if(t-pos>=a)pq.push({ cnt,pos+a*((t-pos) / a) });
        if(t-pos>=b)pq.push({ cnt,pos+b*((t-pos) / b) });
    }
    printf("%d\n", ans);
}