백준: 15708. 미네크래프트 (C++)

1. 문제 정보

• https://www.acmicpc.net/problem/15708
• Platinum V
• 그리디

 

2. 문제 풀이

 

이번 문제도 역시 쉽진 않았어요

처음에 풀이가 생각이 나지 않아 아래 쪽의 알고리즘 분류를 확인하고 감을 잡아 풀었습니다 🥲

우선순위 큐를 활용한 문제였어요

 

 

T = 20, P = 1이라는 조건으로 위의 예시를 볼게요
한 칸 한 칸 옆으로 이동해주며 사용 가능한 총 시간을 계산합니다

위의 예시의 경우 p가 1이므로 한 칸 이동할 때 마다 1씩 감소하게 되겠지요 😀

최대 힙을 이용해 우선순위 큐를 구성하고 미네랄의 위치에서 사용 가능 시간과 미네랄을 비교해 추가가 가능하면 큐에 넣어줍니다

큐의 TOP과 미네랄을 비교했을 때, TOP이 현재 미네랄보다 크다면 제거해줍니다

차례대로 한 번 살펴볼게요 !

 

첫 번째의 경우 사용 가능 시간이 20이고, 이때 시간 소모가 9인 미네랄을 충분히 담을 수 있으므로 큐에 넣어줍니다

 

 

두 번째도 동일한 과정이에요

P = 1이므로 두 번째에 도달했을 때는 사용 가능 시간이 19입니다
그리고 미네랄을 담을 만큼 충분히 시간이 남아 8을 추가로 넣어줍니다 👀

 

 

세 번째 경우인데요, 이때는 추가로 넣으려고 보니 이전 큐의 17에서 8을 더해야해요

그런데 사용 가능 시간인 18을 넘어버리게 됩니다

일단 큐에 7을 넣어주고, 가용 범위인 18이 될 때 까지 TOP에서 하나씩 제거해줍니다

이번 경우는 9만 제거하면 합이 24에서 15가 되므로 큐를 유지할 수 있겠네요 🥰

이런 방식으로 풀게 되면 비교적 쉽게 풀리는 문제였어요 !
아이디어를 떠올리기만 하면 크게 어렵지 않은 문제였습니다 🤗

 

 
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, t, p, x;
int weight = 0;
int ans = 0;
int max_ans = 0;
vector<int> stones;
priority_queue<int> pq;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> t >> p;

    for (int i = 0; i < n; i++) {
        cin >> x;

        stones.push_back(x);
    }

    for (int i = 0; i < n; i++) {
        if (t < i * p) break;

        weight += stones[i];
        pq.push(stones[i]);
        ans++;

        while (!pq.empty() && weight + i * p > t) {
            weight -= pq.top();
            pq.pop();
            ans--;
        }

        max_ans = max(ans, max_ans);
    }

    cout << max_ans;
}