길이가 n인 두 배열 A와 B가 있다고 가정해 보겠습니다. 사용할 수 있는 연산은 다음과 같습니다. 두 개의 인덱스 i와 j를 선택한 후, i번째 요소를 1만큼 감소시키고 j번째 요소를 1만큼 증가시킵니다. 단, 연산을 수행한 뒤에도 배열의 모든 요소는 음수가 아니어야 합니다. 목표는 이 연산을 반복하여 A와 B를 완전히 같게 만드는 것이며, 그때 필요한 연산 순서, 즉 인덱스 쌍의 목록을 찾아야 합니다. 두 배열을 같게 만드는 것이 불가능한 경우에는 -1을 반환합니다.
예를 들어 입력이 A = [1, 2, 3, 4], B = [3, 1, 2, 4]라고 해보겠습니다. 이때 출력은 [(1, 0), (2, 0)]이 됩니다. i = 1, j = 0으로 첫 번째 연산을 수행하면 배열이 [2, 1, 3, 4]가 되고, 이어서 i = 2, j = 0으로 연산하면 [3, 1, 2, 4]가 되어 B와 정확히 일치하기 때문입니다.
문제 해결 단계
이 문제는 아래 단계에 따라 해결할 수 있습니다.
- 합 비교: 배열 A의 총합 a와 배열 B의 총합 b를 각각 구합니다. 이 연산은 한 요소를 줄이고 다른 요소를 늘이는 방식이라 전체 합이 변하지 않으므로, a와 b가 다르면 두 배열을 같게 만드는 것 자체가 불가능합니다. 이 경우 -1을 반환합니다.
- 차이 배열 생성: 각 인덱스별 차이 C[i] = A[i] − B[i]를 계산해 저장하고, 절댓값의 합을 c라고 하면 필요한 연산 횟수는 c / 2입니다.
- 연산 순서 출력: c가 0이 될 때까지 양수인 C[i](A가 더 큰 위치)와 음수인 C[j](B가 더 큰 위치)를 찾아 (i, j)를 출력하고, C[i]는 1 감소, C[j]는 1 증가시킵니다.
a := 0, b := 0, c := 0
n := A의 크기
크기가 n이고 0으로 채워진 배열 C 정의
i := 0부터 i < n까지 i를 1씩 증가시키며 반복:
a := a + A[i]
i := 0부터 i < n까지 i를 1씩 증가시키며 반복:
b := b + B[i]
a ≠ b이면:
-1 반환
그렇지 않으면:
i := 0부터 i < n까지 i를 1씩 증가시키며 반복:
c := c + |A[i] - B[i]|
C[i] := A[i] - B[i]
c := c / 2
i := 0
j := 0
c가 0이 아닌 동안(반복마다 c 1씩 감소):
C[i] <= 0인 동안 i 1씩 증가
C[j] >= 0인 동안 j 1씩 증가
i와 j 출력
C[i] 1 감소, C[j] 1 증가
예제
아래 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A, vector<int> B){
int a = 0, b = 0, c = 0;
int n = A.size();
vector<int> C(n, 0);
for (int i = 0; i < n; i++)
a += A[i];
for (int i = 0; i < n; i++)
b += B[i];
if (a != b){
cout << -1;
return;
}
else{
for (int i = 0; i < n; i++){
c += abs(A[i] - B[i]);
C[i] = A[i] - B[i];
}
c = c / 2;
int i = 0, j = 0;
while (c--){
while (C[i] <= 0)
i++;
while (C[j] >= 0)
j++;
cout << "(" << i << ", " << j << "), ";
C[i]--, C[j]++;
}
}
}
int main(){
vector<int> A = { 1, 2, 3, 4 };
vector<int> B = { 3, 1, 2, 4 };
solve(A, B);
}
입력
{ 1, 2, 3, 4 }, { 3, 1, 2, 4 }
출력
(1, 0), (2, 0),
위 예제에서 배열 A의 총합과 배열 B의 총합은 모두 10으로 같으므로 연산이 가능하며, 총 차이의 절반인 2회의 연산만으로 두 배열을 동일하게 만들 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n + c)로, 배열의 크기와 필요한 연산 횟수에 비례합니다.