[백준 1461번 / C++] 도서관

그리디 문제이다 

 

#접근방법 

 

본인은 우선순위 큐를 적절하게 사용을 해서 풀었다. 이것보다 더 나은 코드가 있다고 생각을 하지만 문제를 보자마자 직관적으로 떠올렸던 풀이방법이였기에 풀었던 방식을 설명하려고 한다. 

 

이 문제에서 중요한 점은 마지막에 책을 갖다 놓고 나면 다시 돌아올 필요없다 라는 것이다. 

 

그리디하게 해당 문제를 접근하기 위해서 위의 문장을 읽고 바로 떠올려야한다. 

 

" 음.. 그러면 가까이 있는 책들을 먼저 갖다놓고 제일 거리가 먼 책을 마지막에 갖다 놔야겠구나"

 

왜냐하면 가장 멀리 있는 놈을 마지막에 갖다 놔야 다시 돌아오는 비용이 추가로 들지 않기 때문이다.

 

먼저 문제에 접근할 때 우선순위 큐 두개를 생성하는데 하나는 음수, 하나는 양수값을 모아놓는다. 

그리고 책의 좌표값을 입력할 때 가장 멀리 있는 좌표값을 미리 체크와 동시에 음수는 음수 큐에 양수는 양수 큐에 넣어준다. 

 

이후, 가장 멀리 있는 좌표값이 음수라면 음수 큐에 가장 윗부분부터 m개 만큼 빼준다. 

왜 m개만큼 빼주냐면 한번에 들고갈 수 있는 책이 m개 니까 음수 좌표에 위치한 책들을 그 만큼 빼줘야한다. 

그리고 result 값에 그 좌표값만 더해준다. 왜냐하면 돌아올 필요가 없기 때문이다. 

 

가장 멀리 있는 좌표값이 양수라면 양수 큐에서 위와 같이 로직을 짜면 된다. 

 

그리고나서 양수 큐 , 음수 큐의 top의 데이터값을 result에 더해주고 m 개 만큼을 pop을 해준다. 

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std; 
priority_queue<int> p_q; 
priority_queue<int, vector<int>, greater<int>>n_q; 
int n, m,result, max_n, max_number; 

void check_nq(int a){
	result += a * n_q.top();
	for (int i = 0; i < m; i++) {
		if (n_q.size()) n_q.pop();
		else return;
	}
}

void check_pq(int a) {
	result += a*p_q.top();
	for (int i = 0; i < m; i++) {
		if (p_q.size()) p_q.pop();		
		else return;
	}
}


int main() {
	cin >> n >> m; 
	vector<int> v(n); 
	for (int i = 0; i < n; i++) { 
		cin >> v[i];
		if (max_n < abs(v[i])) {
			max_number = v[i]; 
			max_n = abs(v[i]); 
		}	
		if (v[i] < 0) n_q.push(v[i]); 		
		else if(v[i]>0) p_q.push(v[i]);		
	}

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

	if (max_number < 0) check_nq(-1); 
	else check_pq(1); 	
	
	while (n_q.size()) 	check_nq(-2); 
	while (p_q.size()) 	check_pq(2);
	
	cout << result; 
	return 0; 

}

 

1461번: 도서관