[BOJ 26939 // C++] Biblioteket

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26939번 문제인 Biblioteket이다.
문제는 아래 링크를 확인하자.

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

26939번: Biblioteket

가장 멀리 꽂아야하는 책 또한 결국 그 위치에 책을 꽂으러 이동해야 하므로, 그 곳으로 책을 꽂으러 갈 때 그 방향으로 꽂아야하는 가장 멀리 있는 책 (최대) K개를 가져갔다가 0으로 돌아오는 그리디 전략으로 책을 채워 문제를 해결하자.

 

위와 같은 왕복이동의 순서는 바꿔도 무방하므로, 위 과정에서 필요한 가장 먼 왕복거리를 마지막 편도이동으로 잡자.

 

아래는 제출한 소스코드이다.

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

int N, K;
vector<int> vec1, vec2;
int ans, mx;

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

	cin >> N >> K;
	while (N--) {
		int x; cin >> x;
		if (x > 0) vec1.emplace_back(x);
		else vec2.emplace_back(-x);
	}

	sort(vec1.begin(), vec1.end());
	sort(vec2.begin(), vec2.end());

	ans = vec1.back() * 2 + vec2.back() * 2;
	mx = max(vec1.back(), vec2.back());
	
	while (vec1.size() > K) {
		for (int k = 0; k < K; k++) vec1.pop_back();
		ans += vec1.back() * 2;
	}
	while (vec2.size() > K) {
		for (int k = 0; k < K; k++) vec2.pop_back();
		ans += vec2.back() * 2;
	}

	ans -= mx;

	cout << ans;
}