문제
접근 방법
가만히 생각해 봅시다… 직선상의 좌표 0에는 우리가 가져다 놓아야할 책들이 있습니다. 책의 원래 자리는 음수부터 양수까지 다양하게 위치해 있죠. 어느 한 좌표를 찍고 좌표 0으로 돌아올 때 걸어야할 거리는 해당 좌표의 절댓값에 2를 곱한 값과 같습니다. 마지막 책을 놓을 때는 좌표 0으로 되돌아오지 않아도 되니 2를 곱하지 않아도 되겠죠.
2를 곱하지 않아도 된다라… 그러면 0을 기준으로, 양 극단에서의(맨 왼쪽 좌표와 맨 오른쪽 좌표) 절댓값이 가장 큰 좌표에 2를 곱하지 않는 것이 유리할 테니, 먼저 양 극단의 절댓값을 비교해 준 후에 더욱 큰 값을 맨마지막에 들르는 좌표로 두겠습니다. 가장 처음에 원래 자리에 가져다 놓는 책의 좌표는 두 절댓값 중 작은 값일 테고요.
처음에 문제에 접근할 때는 이러한 경우들을 생각해 보았습니다.
- 입력 값에 음수 좌표들과 양수 좌표들이 모두 있는 경우.
- 입력 값에 양수 좌표들만 있는 경우.
- 입력 값에 음수 좌표들만 있는 경우.
여러 경우들을 생각해 본 후에, 음수 벡터와 양수 벡터를 각각 하나씩 준비했습니다.
경우 1. 음수 좌표들과 양수 좌표들이 모두 있는 경우.
일단 우리는 좌표 0에서부터 시작합니다. 왼쪽에는 음수 좌표들이 담긴 벡터 negative가 있고, 오른쪽에는 양수 좌표들이 담긴 벡터 positive가 있습니다. 우리는 -negative[0]과 positive[positive.size()-1]의 값을 비교합니다. 이 값들이 좌표 0을 기준으로 양 극단에 있는, 즉 맨왼쪽과 맨오른쪽에 있는 값들이기 때문이죠. 그 중에서 작은 값을 선택해야 합니다. 여기에 또다시 경우가 나뉘겠군요.
1) -negative[0]이 더 작은 경우
우리는 negative 벡터의 인덱스 0부터 오름차순으로 계산을 해 나갈 것입니다. 좌표 0에서 출발할 때 최대로 들 수 있는 책의 수가 M개라고 했으니, negative 벡터의 인덱스 0부터 M을 더해 나가면서 그 인덱스가 negative 배열의 크기를 넘지 않을 때까지의 값들을 모두 더한 값에 2를 곱해야 합니다.
문제는 해당 인덱스에 M을 더한 값이 negative 벡터의 크기를 넘을 때입니다. 이런 경우는 positive 벡터의 원소들을 포함해야 할까요? 이 기준은 어떻게 정할 수 있을까요?
우리는 마지막에 놓을 책의 좌표의 절댓값은 입력된 좌표들의 값들 중 가장 큰 값이길 원합니다. 가장 끝에 있는 책이므로 반드시 들러야 하지만, 이 책의 좌표의 절댓값에 2를 곱하지 않고 싶기 때문이죠.
인덱스에 M을 더해 나가다가 negative 벡터의 크기를 넘게 되는 순간에는 어떻게 해야 할까요? positive 벡터에 대해 같은 과정을 반복해야 합니다. 한 가지 주의할 점은, 우리는 positive 벡터의 가장 큰 값을 담은 인덱스 공간을 반드시 들러야 한다는 것입니다. 그래야만 우리가 입력 받은 모든 책들의 좌표를 들르는 것이 되기 때문이죠. 그렇다면 여기서 합의 최소가 되기 위해서는 어떤 방식으로 인덱스를 넘나 들어야 할까요?
오름차순으로 정렬되어 있는 벡터 공간에서 뒤에 있는 좌표들을 더 들르는 것보다는, 앞에 있는 좌표들을 더욱 들르는 것이 나을 것입니다. 또, 마지막 좌표를 들르기 위해서는 우리가 최대로 들 수 있는 책의 수를 남아 있는 좌표들에서 나누었을 때의 나머지값이 0이 되어야 합니다. 우리가 들러야 할 좌표들의 개수가 우리가 최대로 들 수 있는 책의 개수로 나누어 떨어지려면, 지금의 인덱스로부터 남아 있는 배열 공간의 개수가 M으로 나누어 떨어져야 합니다. 따라서, positive.size() % M의 값만큼 먼저 인덱스를 움직여 줍니다. 그 후에, 인덱스의 값이 positive.size() - 1 과 같아 질 때까지 인덱스에 M 을 더해 나가야 합니다.
2) positive[positive.size()-1]이 더 작은 경우
이 경우는 위의 1) 과 반대 방향으로 진행해 나가야 합니다. positive[positive().size-1]부터 -negative[0] 까지, 위의 과정을 똑같이 밟아 갑니다. 좌표의 부호가 바뀔 때를 유의해 주어야 합니다.
경우 2. 양수 좌표들만 있는 경우.
positive 벡터에서 마지막에 들르는 좌표가 인덱스 positive.size() - 1에 있어야 합니다. 따라서, positive의 인덱스 0에서 먼저 positive.size%M 만큼의 인덱스를 먼저 이동한 후에, 인덱스에 M을 더해 가면서 total 에 해당 값의 절댓값에 2를 곱한 값을 더하여 줍니다. 인덱스 positive.size()-1가 되면, 해당 값에 2를 곱하지 않고 total에 더하여 준 후에 계산을 마칩니다.
경우 3. 음수 좌표들만 있는 경우.
negative 벡터에서 마지막에 들르는 좌표가 인덱스가 0에 있어야 합니다. 따라서, negative의 인덱스 negative.size() - 1 부터 먼저 negative.size%M 만큼의 인덱스를 먼저 이동한 후에, 인덱스에 M을 빼 가면서 total 에 해당 값의 절댓값에 2를 곱한 값을 더하여 줍니다. 인덱스 0이 되면, 해당 값에 2를 곱하지 않고 total에 더하여 준 후에 계산을 마칩니다.
위의 과정들이 말로 해서는 잘 이해 되지 않습니다. 또한 너무 복잡하여 오류가 발생했을 때 어디가 틀렸는지 알아차리기도 쉽지 않고요. 실제로 코드를 짜는데 오랜 시간이 걸렸고, 백준 사이트에 업로드 했을 때 [틀렸습니다]가 나왔습니다. 오류가 어디에서 나는지도 알아차리기가 힘들었습니다. 또한 이런저런 코너 케이스가 계속 발생했습니다. 예를 들면 이런 경우들이지요:
1. N < M 인 경우
2. N == M 인 경우
3. N > M 인 경우
코드를 보면 저의 접근 방식을 이해하기가 훨씬 수월할 것입니다:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
// 이거 치면 printf 만큼 빨라짐.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
vector<int> negative;
vector<int> positive;
int num;
for (int i = 0; i < N; i++) {
cin >> num;
if (num > 0) positive.push_back(num);
else negative.push_back(num);
}
// negative, positive 오름차순 정렬.
sort(negative.begin(), negative.end());
sort(positive.begin(), positive.end());
// negative[0] 와 positive[positive.size()-1] 중
// 절댓값이 작은 것부터 시작.
// 단, negative 배열의 크기가 0이거나 positive 배열의 크기가 0인 경우가 있을 수 있음.
int total = 0;
int index;
if (N >= M) {
if (negative.empty()) {
// negative 배열의 크기가 0이라면. 즉, 음수가 없다면
if (positive.size()%M == 0) {
index = M-1;
} else {
index = positive.size()%M-1;
}
while (1) {
if (index >= positive.size() - 1) {
total += positive[positive.size()-1];
break;
} else {
total += positive[index] * 2;
}
index += M;
}
} else if (positive.empty()) {
// positive 배열의 크기가 0이라면. 즉, 양수가 없다면.
if (negative.size()%M == 0) {
index = negative.size()-M;
} else {
index = negative.size()-negative.size()%M;
}
while (1) {
if (index <= 0) {
total += (-negative[0]);
break;
} else {
total += (-negative[index] * 2);
}
index -= M;
}
} else {
//negative와 positive 중 어느 것도 크기가 0이 아닌 경우.
// |negative[0]|이 |positive[positive.size()-1]|보다 작은 경우.
if (-negative[0] < positive[positive.size()-1]) {
index = 0;
while (index < negative.size()) {
total += (-negative[index]*2);
index += M;
}
// 만약 남은 갯수가 positive 배열의 mod 값보다 크거나 같다면.
// positive 배열의 mod 만큼의 모든 수를 포함해야 함.
if(positive.size()%M != 0 && M >= negative.size()-index + negative.size()%M) {
total += (positive[positive.size()%M-1] * 2);
index = positive.size()%M-1;
} else {
index = -1;
}
// positive 배열의 모든 남은 수에 대하여 계산.
while (1) {
index += M;
if (index >= positive.size()-1) {
total += positive[index];
break;
}
total += (positive[index]*2);
}
} else {
// positive[positive.size()-1] 이 |negative[0]| 보다 작은 경우.
index = positive.size() - 1;
while (index >= 0) {
total += positive[index];
index -= M;
}
total *= 2;
if (index >= 0 && M >= negative.size()%M + index + 1) {
total += (-negative[negative.size()-negative.size()%M] * 2);
index = negative.size()-negative.size()%M;
} else {
index = negative.size()-negative.size()%M;
}
while (1) {
if (index <= 0) {
total += -negative[0];
break;
}
total += (-negative[index] * 2);
index -= M;
}
}
}
} else {
if (negative.empty()) {
total += positive[positive.size()-1];
} else if (positive.empty()) {
total += -negative[0];
} else {
// positive[positive.size()-1] 과 |negative[0]| 을 비교.
if (-negative[0] < positive[positive.size()-1]) {
total += (-negative[0] * 2 + positive[positive.size()-1]);
} else {
total += (positive[positive.size()-1] * 2 - negative[0]);
}
}
}
cout << total;
}슬쩍 다른 이들의 코드를 살펴보니, 코드가 이보다 훨씬 짧았습니다. 그래서 저는 분명 다른 간단한 방법이 있을 거라고 생각했죠. 실제로 더욱 간단한 풀이를 떠올리는 데에 성공하였습니다.
더욱 간단한 풀이
입력 값을 받아 모두 같은 벡터 v에 넣습니다. 0을 포함하여 넣을게요. 그리고 이 벡터를 먼저 오름차순으로 정렬해 줍니다. 위의 풀이와 다르게 negative 벡터, positive 벡터로 나누지 않고 한 벡터에 넣는다는 점을 주의해야 합니다. 그리고 양 극단에 있는 수들의 절댓값을 비교합니다. abs(v[0])과 abs(v[v.size()-1])를 비교했을 때, 만약 abs(v[v.size()-1])의 값이 더 작다면 이 벡터를 내림차순 정렬로 바꾸어주고, 그렇지 않다면 그대로 계산을 진행합니다.
인덱스 0부터 시작하여 해당 값들의 좌표가 바뀌지 않을 때까지 인덱스에 M을 더해 가면서 각 절댓값에 2를 곱한 값을 우리가 구할 최종 값인 total 에 더하여 줍니다. 좌표들이 바뀌는 것은 v[index]와 v[index+M]을 곱했을 때 그 수가 음수가 된다면 index부터 index + M 사이에 0이 존재한다는 것이고, 0이 된다면 v[index+M]이 0이 된다는 뜻입니다.
v[index] * v[index+M]이 음수가 될 때, 즉, 좌표들의 부호가 바뀔 때 우리는 벡터 공간의 값이 0이 되는 인덱스를 먼저 찾아야 합니다.
그리고 벡터의 마지막 인덱스에 있는 공간을 반드시 들러야 하기 때문에, 그리고 그 안에서 우리가 더할 값들이 최소가 되어야 하기 때문에, 우리는 먼저 index += (v.size()-index-1)%M를 해주어 현재의 인덱스에서부터 마지막 인덱스까지 남은 공간이 M으로 나누어 떨어지도록 만들어 줍니다. 그 후에 인덱스가 v.size()-1보다 작을 때까지 M을 더해주다가 인덱스가 v.size()-1이 되었을 때는 이 절댓값에 2를 곱하는 것이 아니라 1을 곱한 값만 더하여 계산을 마무리 합니다.
다시 한 번 코드로 설명을 하자면:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib> // abs for int, long int
using namespace std;
bool desc (int x, int y) {
return x > y;
}
int main()
{
// 이거 치면 printf 만큼 빨라짐.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
vector<int> v;
v.push_back(0);
int num;
int min = 1000000;
int max = 0;
for (int i = 0; i < N; i++) {
cin >> num;
v.push_back(num);
if (num > max) max = num;
if (num < min) min = num;
}
if (abs(min) > abs(max)) {
sort(v.begin(), v.end(), desc);
} else {
sort(v.begin(), v.end());
}
int total = 0;
int index = 0;
while (1) {
// cout << "index: " << index << " " << v[index] << endl;
total += abs(v[index] * 2);
if (index+M < v.size()-1 && v[index]*v[index+M] <= 0) {
while (v[index] != 0) {
index++;
}
if ((v.size()-index-1)%M == 0) index += M;
else if ((v.size()-index-1)%M+index < v.size()-1) index += (v.size()-index-1)%M;
else {
total += abs(v[v.size()-1]);
break;
}
} else {
index += M;
}
if (index >= v.size() - 1) {
total += abs(v[v.size()-1]);
break;
}
}
cout << total;
}중간에 v[index] * v[index+M] 이 0이 되는 경우에 대한 처리를 잘 해주지 않아서 [시간초과]가 여러 번 발생했었지만, 다행히도 빨리 고칠 수 있었습니다. 결과는 성공입니다!!
문제를 풀면서 느낀 것은?
사실 머리가 되게 복잡했습니다. 처음의 접근 방법으로는 나누어야 할 경우들이 많았고, 각각의 경우들마다 코너 케이스가 생기는 골치 아픈 일들이 발생했기 때문이죠. 코드를 줄이기 위해서 분명히 방법이 있을 것이라고 생각하고 포기하지 않고 더욱 간단한 방법을 생각해내어 아이디어를 떠올려 낸 것에 대해서 뿌듯합니다.
인내, 즐거움, 성장. 그저 하루하루, 꾸준히 해나가다 보면. 그리고 그 과정 자체를 즐길 수만 있다면. 저는 그것으로 행복합니다. 따라서 이런 알고리즘 문제를 매일 푸는 것이 그저 즐겁습니다.