[백준] 1461번 도서관 (C++)

문제

 

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

---

풀이

이 문제는 그리디 문제로, 절댓값이 가장 큰 책을 마지막에 갖다놓는(0으로 안돌와도 됨) 방법으로 풀이했다.

 

1. 음수, 양수 값을 나눠서 벡터에 저장(음수는 양수로 변환하여 저장)하고, 절댓값이 가장 큰 값을 저장한다.
2. 각 벡터를 내림차순 정렬한다.
3. idx 번째 값의 * 2 한 값을 sum에 더하고 idx + m하는 과정을 벡터의 크기 만큼 반복한다.
4. 이때, 가장 큰 값이 존재하는 벡터일 경우,  왕복 값이 아닌 편도 값을 먼저 더한 뒤, 3번 과정을 반복한다.

#include<iostream>
#include<vector>
#include<algorithm>

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

using namespace std;


vector <int> plusVec;
vector <int> minusVec;
int n, m;

bool cmp(int a, int b) {
	return a > b;
}

int Search(vector<int> vec, bool isTopValue) {
	 int idx = 0, sum = 0;

	 if (vec.size() == 0)
		 return 0;

	if (isTopValue) { // 가장 큰 값이 있을 때,
	
		sum += vec[idx];
		idx += m;

		if (vec.size() <= idx)
			return sum;
	}

	while (true) { // 왕복 값 구하기
		sum += vec[idx] * 2;
		idx += m;

		if(vec.size() <= idx)
			return sum;
	}
}

int main() {

	cin >> n >> m;

	int input, maxValue = 0;
	for (int i = 0; i < n; i++) {
		cin >> input;

		if (input > 0)
			plusVec.push_back(input);
		else
			minusVec.push_back(input * -1);

		if (abs(maxValue) < abs(input))
			maxValue = input;
	}
	

	// 내림차순 정렬
	sort(plusVec.begin(), plusVec.end(), cmp);
	sort(minusVec.begin(), minusVec.end(), cmp);

	bool isPlusHigh = maxValue > 0;
	cout << Search(plusVec, isPlusHigh) + Search(minusVec, !isPlusHigh);

	return 0;
}