백준 20956번 아이스크림 도둑 지호

🔒[문제 url]

https://www.acmicpc.net/problem/20956

🔑알고리즘

minHeap과 maxHeap을 선언하여, 둘 다 양이 많은 아이스크림부터 내림차순으로 삽입한다.

• 두 heap은 같은 양의 아이스크림을 삽입할 때 차이를 갖는다.
  • minHeap에는 아이스크림의 번호가 작은 것부터 삽입한다.
  • maxHeap에는 아이스크림의 번호가 큰 것부터 삽입한다.

---

1. minHeap.top()부터 먹기 시작한다.
   먹은 아이스크림을 구별하기 위해, 먹을 때마다 visited 배열에 아이스크림 번호를 표시한다.
2. $i$번 아이스크림을 이미 먹었다면, 즉 visited[i] == true라면 pop 한다.
3. minHeap.top()을 먹었는데 민트초코 맛이라면, 즉 7로 나누어 떨어진다면 다음엔 maxHeap.top()을 먹게된다.
   마찬가지로 maxHeap.top()을 먹었는데 민트초코 맛이라면, 즉 7로 나누어 떨어진다면 다음엔 minHeap.top()을 먹게된다.**
4. 먹을 때마다 heap의 원소를 pop 해준다.

🐾부분 코드

int n,m;
int A;

typedef pair<int,int> pii;
struct comp
{
    bool operator()(pii a,pii b)
    {
        if(a.first == b.first) return a.second > b.second;//오름차순
        else return a.first < b.first;//내림차순
    }
};
priority_queue<pii,vector<pii>,comp> minHeap;//작은 인덱스가 먼저
priority_queue<pii> maxHeap;//큰 인덱스가 먼저
bool visited[100001];
bool isReversed = false;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> A;
        minHeap.push({A,i});
        maxHeap.push({A,i});
    }
}

<변수 선언 및 입력 함수>

• minHeap의 정렬 기준을 구현한다.
  양이 같다면, 번호가 작은 것이 앞으로 온다.
  maxHeap의 정렬 기준은 default이다.
• visited[i] : $i$번 아이스크림은 이미 먹었음을 의미한다.
• isReversed : 순서의 뒤집힘 여부를 판별한다.

void SOLVE()
{
    while(m--)
    {
        if(isReversed)
        {
            while(visited[maxHeap.top().second]) maxHeap.pop();
            if(maxHeap.top().first % 7 == 0) isReversed = !isReversed;
            cout << maxHeap.top().second << '\n';
            visited[maxHeap.top().second] = true;
            maxHeap.pop();
        }
        else
        {
            while(visited[minHeap.top().second]) minHeap.pop();
            if(minHeap.top().first % 7 == 0) isReversed = !isReversed;
            cout << minHeap.top().second << '\n';
            visited[minHeap.top().second] = true;
            minHeap.pop();
        }
    }
}

<아이스크림 먹기>
순서가 뒤집혀있을 경우 maxHeap에서, 아닌 경우 minHeap에서 먹을 아이스크림을 찾는다.

🪄전체 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n,m;
int A;

typedef pair<int,int> pii;
struct comp
{
    bool operator()(pii a,pii b)
    {
        if(a.first == b.first) return a.second > b.second;//오름차순
        else return a.first < b.first;//내림차순
    }
};
priority_queue<pii,vector<pii>,comp> minHeap;//작은 인덱스가 먼저
priority_queue<pii> maxHeap;//큰 인덱스가 먼저
bool visited[100001];
bool isReversed = false;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> A;
        minHeap.push({A,i});
        maxHeap.push({A,i});
    }
}


void SOLVE()
{
    while(m--)
    {
        if(isReversed)
        {
            while(visited[maxHeap.top().second]) maxHeap.pop();
            if(maxHeap.top().first % 7 == 0) isReversed = !isReversed;
            cout << maxHeap.top().second << '\n';
            visited[maxHeap.top().second] = true;
            maxHeap.pop();
        }
        else
        {
            while(visited[minHeap.top().second]) minHeap.pop();
            if(minHeap.top().first % 7 == 0) isReversed = !isReversed;
            cout << minHeap.top().second << '\n';
            visited[minHeap.top().second] = true;
            minHeap.pop();
        }
    }
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

도대체 민트초코를 왜 먹는가? 그렇지만 도둑질은 안 된다!
가운데를 말해요 덕에 pq 활용력이 올라 쉽게 풀 수 있었다.
가운데를 말해요는 진짜 ptsd 온다...