https://www.acmicpc.net/problem/1461
1461번: 도서관
세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책
www.acmicpc.net
코드
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int N, M, l, r, ans;
vector<int> arr;
int main() {
fastio();
cin >> N >> M;
arr = vector<int>(N);
for (int i = 0; i < N; i++) cin >> arr[i];
sort(arr.begin(), arr.end());
l = 0; r = N - 1;
if (N == 1) cout << arr[0];
else {
// starting
if (abs(arr[0]) < abs(arr[N - 1])) {
for (int i = r; i >= N - M and i >= 0; i--) if (0 < arr[i]) r--;
ans += abs(arr[N - 1]);
}
else {
for (int i = l; i < M and i < N; i++) if (arr[i] < 0) l++;
ans += abs(arr[0]);
}
// while
while (l <= r) {
if (abs(arr[l]) < abs(arr[r])) {
int R = r;
for (int i = R; i > R - M and i >= 0; i--) if (0 < arr[i]) r--;
ans += abs(arr[R]) * 2;
}
else {
int L = l;
for (int i = L; i < L + M and i < N; i++) if (arr[i] < 0) l++;
ans += abs(arr[L]) * 2;
}
if (l == 0 and r == 0) {
ans += abs(arr[0]) * 2;
break;
}
}
cout << ans;
}
}
|
cs |
풀이
https://wantchicken.tistory.com/120
백준 12904: A와 B [C/C++]
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), AB..
wantchicken.tistory.com
12904문제와 마찬가지로 뒤에서 풀어주는 아이디어를 생각하면 쉽게 풀리는 문제였습니다.
8 3
-45 -26 -18 -9 -4 22 40 50주어진 예제를 정렬하였습니다
문제 조건 중 '책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다' 라고하니, 절대값이 가장 큰 값은 가장 나중에 가야 합니다.
1. 먼저 가장 절대값이 큰 것을 처리해 줍니다.
0에서 50으로 갈 때, 50만큼 걸어야 합니다.
2. 그 이후 가장 먼 값을 차례대로 지워줍니다
세준이는 한 번에 최대 M권의 책을 들 수 있다라는 조건이 있으니, 이동 시 최대한 여러 권을 가장 먼 곳으로 가져가고, 가장 먼 곳으로부터 가까운 M - 1개에 책을 나둡니다.