문제 소개
크기가 같은 두 배열 X와 Y가 주어졌다고 가정해 보겠습니다. 첫째 날에는 i번째 위치에 X[i]개의 돌을 가진 더미가 있고, 둘째 날에는 같은 위치에 Y[i]개의 돌이 있다고 합니다. 이틀 사이에 여러 사람이 돌 더미를 방문했으며, 이들이 할 수 있는 행동은 다음 세 가지뿐입니다.
- 아무것도 하지 않는다
- 어떤 더미에 돌 몇 개를 추가한다
- 한 더미에서 다른 더미로 돌 몇 개를 옮긴다
이때 우리가 확인해야 할 것은 Y가 X로부터 실제로 발생할 수 있는 유효한 상태인지 여부입니다.
예를 들어 입력이 X = [1, 2, 3, 4, 5], Y = [2, 1, 4, 3, 5]라면 출력은 True입니다. 두 번째 더미에서 첫 번째 더미로 돌 하나를 옮기고, 네 번째 더미에서 세 번째 더미로 돌 하나를 옮기면 되기 때문입니다.
접근 방식: 총합 비교
핵심 아이디어는 매우 간단합니다. 허용된 연산의 특성을 살펴보면 다음과 같습니다.
- 돌 옮기기: 한 더미에서 빼서 다른 더미에 넣는 것이므로 전체 돌의 총개수는 변하지 않습니다.
- 돌 추가하기: 전체 돌의 총개수를 늘립니다.
- 돌을 없애는 행위는 허용되지 않으므로 총개수가 줄어드는 경우는 없습니다.
따라서 Y의 돌 총합이 X의 돌 총합보다 크거나 같다면 Y는 유효한 상태입니다. 반대로 총합이 줄어들었다면 누군가 돌을 제거했다는 뜻이므로 유효하지 않습니다.
단계별 풀이
다음 단계를 따라 문제를 해결할 수 있습니다.
- 첫째 날 배열 A의 모든 원소를 더해 s를 구합니다.
- 둘째 날 배열 B의 모든 원소를 더해 d를 구합니다.
- d가 s보다 크거나 같으면 true를, 그렇지 않으면 false를 반환합니다.
n := size of A
s := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
s := s + A[i]
d := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
d := d + B[i]
return (if d >= s, then true, otherwise false)
C++ 구현 예제
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, vector<int> B){
int n = A.size(), d = 0, s = 0;
for (int i = 0; i < n; i++)
s += A[i];
for (int i = 0; i < n; i++)
d += B[i];
return d >= s ? true : false;
}
int main(){
vector<int> X = { 1, 2, 3, 4, 5 };
vector<int> Y = { 2, 1, 4, 3, 5 };
cout << solve(X, Y) << endl;
}
입력
{ 1, 2, 3, 4, 5 }, { 2, 1, 4, 3, 5 }
출력
1
X의 총합은 15이고 Y의 총합 역시 15입니다. 즉, 돌을 새로 추가할 필요 없이 기존 돌들을 재배치하는 것만으로 Y 상태를 만들 수 있으므로 함수는 true(1)를 반환합니다.
복잡도 분석
이 풀이는 각 배열을 한 번씩 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리를 사용하지 않는 O(1) 공간 복잡도로 해결됩니다.