PS/BOJ
백준 1461번: 도서관 (C++)
도비(Doby)
2022. 11. 3. 23:46
https://www.acmicpc.net/problem/1461
1461번: 도서관
세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책
www.acmicpc.net
Solved By: Greedy, Sort
우선 0을 기준으로 양수와 음수를 넘나드는 것은 비효율적이기 때문에 0을 시작점으로 두고 음수에 대해서만 생각해봤습니다.
테스트 케이스 1에서 음수 값들을 모두 절댓값 크기 순대로 정렬하면 {39, 37, 29, 28, 6}과 같은 순으로 나옵니다.
M = 2이기 때문에 {39, 37}, {29, 28}, {6}으로 가서 39 * 2 + 29 * 2 + 6 = 142라는 결과를 가져올 것인지
{6}, {29, 28}, {39, 37} 순으로 가서 6 * 2 + 29 * 2 + 39 = 109라는 결과를 가져올 것인지 나누어볼 수 있었습니다.
즉, 멀리 있는 것부터 갔다 올 것이냐 or 가까이 있는 것부터 갔다 올 것이냐를 선택하면 됩니다. (그리디)
당연하게도 어떤 한 책을 갔다 두는 데에도 거리를 2번 걸으니 가까운 곳 2번 걷는 것이 최소 선택지입니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> pa, ma;
int getSum(vector<int>& v){
if(v.empty()) return 0;
int ret = 0;
for(int i = 0; i < v.size(); i += M){
ret += v[i] * 2;
}
return ret;
}
bool cmp(int a, int b){
return a > b;
}
int main(){
cin >> N >> M;
for(int i = 0; i < N; i++){
int b; cin >> b;
if(b > 0) pa.push_back(b);
else ma.push_back(-b);
}
sort(pa.begin(), pa.end(), cmp);
sort(ma.begin(), ma.end(), cmp);
int res_p = getSum(pa);
int res_m = getSum(ma);
int m_value;
if(pa.empty()) m_value = ma[0];
else if(ma.empty()) m_value = pa[0];
else m_value = max(ma[0], pa[0]);
cout << res_p + res_m - m_value;
return 0;
}