백준 2786, 상근이의 레스토랑

문제

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

풀이

보고 풀었다. 근데도 틀려서 한번 더 봤다... 코드는 진짜 멘탈이 나가서 스파게티코드로 짯기 때문에 보지 않는 것을 추천한다.

풀이는 다른 분 벨로그에 있는 풀이를 사용하되 내가 틀린 부분에 대해서만 자세히 설명하겠다. 다른 분은 다른 방식을 사용하셨던데 봐도 잘 모르겠어서 나는 우선순위 큐를 썻다.

기본적으로 0 ~ i의 음식 B를 다 더해서 구한다.

이때 두가지를 통해 하나의 A 음식을 선정할 수 있다.

1. 0 ~ i-1의 A - B가 가장 작은 것을 고른다.
2. i ~ n-1의 A가 가장 작은 것을 고른 뒤 가장 큰 B(B는 정렬되어 있으므로 가장 최신을 빼내면 된다)를 넣는다.

우선순위 큐를 통해 최소를 관리하는 방식으로 진행했다. 이때 A의 최소를 관리할때는 이미 뽑은 것은 없애야 하는데 그냥 멍청하게 i를 기준으로 했다가 시간이 오래 걸렸다. 이와 비슷한 생각을 처음에도 했었는데 그때는 엄청 어렵게 생각해서 코드가 깔끔하게 안나오고 i도 이상하게 해서 틀리지 않았나 싶다.

벽느껴진다.

실수

• i 기준이 아니라 B를 정렬했으니까 방문한 것을 기준으로 생각해야 한다.
• 쉽게 생각 못해서 구현도 처음에 엄청 꼬였다.
• 쉽게 쉽게, 구현은 정확하게, 입력 과 출력을 잘 확인하자.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>

using namespace std;

vector<pair<int, int>> diff;
vector<pair<int, int>> A;
vector<pair<int, int>> B; // 이건 정렬 

priority_queue<pair<int, int>> pq_A;
priority_queue<pair<int, int>> pq_diff;

vector<int> visit(500000, 0);

int n;

int main() {

	scanf("%d", &n);

	long long int temp1, temp2;

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

		scanf("%lld %lld", &temp1, &temp2);
		
		diff.push_back(make_pair(temp1 - temp2, i));
		A.push_back(make_pair(temp1, i)); 
		B.push_back(make_pair(temp2, i));// 작은 순서대로 보기위해 음수화

		pq_A.push(make_pair(-1 * A[i].first, A[i].second));// 작은 순서대로 보기위해 음수화

	}

	sort(B.begin(), B.end());

	long long int sum_B = 0; // 0 ~ i-1의 B의 합
	
	for (int i = 0; i < n; i++) {

		pq_diff.push(make_pair(B[i].first - A[B[i].second].first, B[i].second)); // A - B

		sum_B += B[i].first;
		visit[B[i].second] = 1;

		while (!pq_A.empty() && visit[pq_A.top().second]) // 이미 방문했으면 pop
			pq_A.pop();

		temp1 = sum_B + pq_diff.top().first * -1; // 0 ~ i-1 에서 A를 택할 경우 diff만 더하면 됨

		if (pq_A.empty()) // i ~ n-1에서 A를 택할 경우 가장 비싼 B를 버림
			temp2 = 600000000000000;

		else
			temp2 = sum_B + pq_A.top().first * -1 - B[i].first; // 가장 비싼 B는 가장 최신임

		printf("%lld\n", min(temp1, temp2));

	}

	return 0;

}