배열 A에 서로 다른 n개의 원소가 들어 있고, 또 하나의 수 x가 주어져 있다고 가정해 봅시다. 여기에는 n개의 금 조각이 있으며, i번째 금 조각의 무게는 A[i]입니다. 우리는 이 n개의 금 조각을 한 번에 하나씩 저울 위에 올려야 합니다. 그런데 이 저울에는 특이한 결함이 하나 있는데, 바로 저울 위의 총 무게가 정확히 x가 되는 순간 폭발해 버린다는 것입니다.
따라서 우리는 n개의 금 조각 전부를 적절한 순서로 올려서 과정 중에 저울이 폭발하지 않도록 할 수 있는지 판단해야 합니다. 가능하다면 그 순서를 찾아 출력하고, 불가능하다면 "IMPOSSIBLE"을 표시하면 됩니다.
예를 들어 입력이 A = [1, 2, 3, 4, 8], x = 6이라면 출력은 [8, 1, 2, 3, 4]가 됩니다. 물론 이 외에도 유효한 순서는 여러 가지가 존재할 수 있습니다.
문제 해결 접근 방식
이 문제를 해결하기 위해 다음 단계를 따릅니다. 먼저 핵심 아이디어를 살펴보겠습니다.
모든 금 조각의 무게 합이 x와 같다면, 마지막 조각을 올리는 순간 반드시 폭발하게 되므로 어떤 순서를 사용해도 해답이 존재하지 않습니다. 이 경우 "IMPOSSIBLE"을 출력합니다.
반대로 총합이 x가 아니라면, 금 조각을 차례대로 올리면서 누적 합을 추적합니다. 누적 합이 x가 되어 버리는 지점에서는 현재 원소와 바로 다음 원소의 순서를 맞바꿔 출력하면 됩니다. 두 원소의 위치를 교환하면 해당 시점의 누적 합이 달라지기 때문에, 총합이 x와 정확히 일치하는 상황을 피할 수 있습니다.
알고리즘 의사 코드
s := 0
n := A의 크기
i := 0부터 시작하여 i < n인 동안 i를 1씩 증가시키며 반복:
s := s + A[i]
만약 s == x라면:
"IMPOSSIBLE" 반환
s := 0
i := 0부터 시작하여 i < n인 동안 i를 1씩 증가시키며 반복:
s := s + A[i]
만약 s == x라면:
A[i + 1], A[i] 출력
i를 1 증가
이후 부분은 건너뛰고 다음 반복으로 진행
A[i] 출력
예제
더 나은 이해를 돕기 위해 다음 C++ 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A, int x) {
int s = 0;
int n = A.size();
for (int i = 0; i < n; i++) {
s += A[i];
}
if (s == x) {
cout << "IMPOSSIBLE";
return;
}
s = 0;
for (int i = 0; i < n; i++) {
s += A[i];
if (s == x) {
cout << A[i + 1] << ", " << A[i] << ", ";
i++;
continue;
}
cout << A[i] << ", ";
}
}
int main() {
vector<int> A = { 1, 2, 3, 4, 8 };
int x = 6;
solve(A, x);
}
입력
{ 1, 2, 3, 4, 8 }, 6출력
1, 2, 4, 3, 8,
출력 결과를 살펴보면, 1 + 2 + 3 = 6으로 누적 합이 x와 일치하게 되는 지점에서 3과 4의 순서를 맞바꿔 1, 2, 4, 3, 8 순서로 출력된 것을 확인할 수 있습니다. 이렇게 하면 어느 시점에서도 저울 위의 총 무게가 정확히 6이 되지 않으므로 저울은 폭발하지 않고 모든 금 조각을 안전하게 올릴 수 있습니다.