백준 1461 c++ "도서관" -PlusUltraCode-

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

 

[필자 사고]

그리디 문제이다.

필자는 우선순위큐를 이용하여 M개 만큼 빼는 형태로 해당 문제를 해결했다.

음수와 양수를 따로 처리를 해줬고 절대값이 가장 큰 값은 복귀를 하지 않아도 되므로

해당 부분은 따로 찾은 뒤 pop을 해결했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

구조 설명

1. 입력 받기 (Input)
   • N개의 수를 입력받습니다.
   • 수를 절댓값과 부호(1: 양수, 0: 음수)로 저장해둡니다 (arr 벡터).
   • 양수는 plus_Queue에, 음수는 minus_Queue에 각각 저장합니다.
     • plus_Queue는 큰 수가 우선 나오게 (오름차순)
     • minus_Queue는 작은 수가 우선 나오게 (내림차순) 정렬합니다.
   • 전체 입력 중 가장 절댓값이 큰 수가 양수인지 음수인지 체크하여 maxFlag에 저장합니다.
2. 우선순위 큐에서 수 꺼내기 (pqPop)
   • flag에 따라 plus 큐 또는 minus 큐 중 하나를 선택합니다.
   • 가장 큰 (또는 작은) 수를 하나 꺼내어 그 절댓값을 저장합니다.
   • M개 만큼 큐에서 값을 꺼내어 삭제합니다 (한 번 갈 때 여러 물건을 옮기는 느낌).
   • findMaxPop이 true라면 편도 이동으로 계산해서 절댓값 그대로 리턴하고,
     아니라면 왕복 이동이라 절댓값 ×2 해서 리턴합니다.
3. 게임 시작 (Game_Start)
   • 가장 절댓값이 큰 쪽 (maxFlag)에 대해 처음은 편도 이동으로 계산합니다.
   • 이후 나머지 모든 plus_Queue와 minus_Queue는 왕복 이동으로 계산합니다.
   • 이동 거리 합계를 최종적으로 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

int N, M;
vector<pair<int,int>> arr;
int maxFlag = 0;

struct cmp1 {
	bool operator()(int a, int b) {
		return a < b;
	}
};
struct cmp2 {
	bool operator()(int a, int b) {
		return a > b;
	}
};

priority_queue<int, vector<int>,cmp1> plus_Queue;
priority_queue<int, vector<int>,cmp2> minus_Queue;

void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		int flag = (num > 0) ? 1 : 0;
		arr.push_back({ abs(num),flag });
		if (num < 0) {
			minus_Queue.push(num);
		}
		else {
			plus_Queue.push(num);
		}
	}
	auto it = max_element(arr.begin(), arr.end());
	if (it->second == 0) {
		maxFlag = -1;
	}
	else {
		maxFlag = 1;
	}
}

int pqPop(int flag, bool findMaxPop) {
	int count = 0;
	
	if (flag == -1) {
		count = abs(minus_Queue.top());
		int popCount = 0;
		while (!minus_Queue.empty()&&popCount!=M) {
			minus_Queue.pop();
			popCount++;
		}
	}

	else {
		count = abs(plus_Queue.top());
		int popCount = 0;
		while (!plus_Queue.empty() && popCount != M) {
			plus_Queue.pop();
			popCount++;
		}
	}

	if (findMaxPop == true) {

		return count;
	}

	return 2*count;
}

void Game_Start() {
	int resultCount = 0;

	if (maxFlag == 1) {
		resultCount +=pqPop(1, true);
	}
	else {
		resultCount+=pqPop(-1, true);
	}


	while (!minus_Queue.empty()) {
		resultCount += pqPop(-1, false);
	}
	while (!plus_Queue.empty()) {
		resultCount += pqPop(1, false);
	}

	cout << resultCount;
}

int main(void) {
	Input();
	Game_Start();
}