C++로 여러 번의 합 연산을 통해 목표 배열 만들기

정수로 이루어진 목표 배열 target이 주어졌다고 가정해 봅시다. 모든 원소가 1로 구성된 시작 배열 A에서 다음과 같은 작업을 수행할 수 있습니다.

현재 배열에 있는 모든 원소의 합을 x라고 합니다.
0부터 n 사이의 인덱스 i를 선택하고(n은 배열의 크기), 배열 A의 i번째 값을 x로 설정합니다.
이 과정은 필요한 만큼 몇 번이든 반복할 수 있습니다.

우리가 해야 할 일은 시작 배열 A에서 목표 배열 target을 만드는 것이 가능한지 판별하고, 불가능하다면 false를 반환하는 것입니다.

예를 들어 입력이 [3, 9, 5]라면 출력은 true가 됩니다. [1, 1, 1]에서 시작해 인덱스 0에 현재 합인 3을 넣으면 배열은 [3, 1, 1]이 되고, 이어서 인덱스 2에 합 5를 넣으면 [3, 1, 5], 마지막으로 인덱스 1에 합 9를 넣어 [3, 9, 5]를 얻을 수 있기 때문입니다.

해결 접근 방법

이 문제는 순방향보다 역방향으로 거슬러 올라가는 방식으로 접근하는 것이 효율적입니다. 배열에서 가장 큰 값은 항상 마지막에 새로 채워진 값이므로, 그 값을 되돌리면 이전 단계의 배열 상태를 알아낼 수 있습니다. 이때 최대값을 빠르게 찾기 위해 우선순위 큐(최대 힙)를 활용합니다.

구체적인 단계는 다음과 같습니다.

sum := 0으로 초기화합니다.
n := target의 크기로 설정합니다.
i := 0부터 n 미만까지 반복하며 sum := sum + target[i]를 수행해 전체 합을 구합니다.
target 배열의 원소들로 초기화한 우선순위 큐 pq를 정의합니다.
pq의 최상단 원소 × 2 > sum인 동안 다음을 반복합니다.
- x := pq의 최상단 원소
- pq에서 해당 원소를 제거합니다.
- pq에 2 * x − sum을 삽입합니다. (마지막 연산 직전의 값)
- sum := x로 갱신합니다.
반복이 끝난 뒤 sum이 target의 크기와 같으면 true, 아니면 false를 반환합니다.

핵심 아이디어는 다음과 같습니다. 현재 최대값 x와 나머지 원소들의 합(sum − x)이 있을 때, x는 마지막에 전체 합으로 덮어써진 값이므로 한 단계 이전의 값은 2x − sum이 됩니다. 이 과정을 계속 진행했을 때 결국 모든 원소가 1로 수렴한다면 목표 배열을 만드는 것이 가능하다는 의미입니다.

다음 구현 예제를 통해 더 잘 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    bool isPossible(vector<int>& target) {
       lli sum = 0;
       int n = target.size();
       for (int i = 0; i < n; i++) {
           sum += target[i];
       }
       priority_queue<int> pq(target.begin(), target.end());
       while (pq.top() * 2 > sum) {
           int x = pq.top();
           pq.pop();
           pq.push(2 * x - sum);
           sum = x;
       }
       return sum == (int)target.size();
   }
};
main(){
    Solution ob;
    vector<int> v = {3,9,5};
    cout << (ob.isPossible(v));
}

입력

{3,9,5}