C++로 두 친구에게 사탕 가방을 공평하게 나누어 줄 수 있는지 확인하는 프로그램

문제 이해하기

4개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 사탕 가방이 총 4개 있으며, i번째 가방에는 A[i]개의 사탕이 들어 있습니다. 우리는 이 가방들을 두 친구에게 나누어 주려고 하는데, 이때 각 친구가 받는 사탕의 총 개수가 같아지도록 배분할 수 있을지 확인해야 합니다.

예를 들어 입력이 A = [1, 7, 11, 5]라고 해보겠습니다. 이 경우 출력은 True(참)입니다. 첫 번째와 세 번째 가방(1 + 11 = 12)을 한 친구에게, 두 번째와 네 번째 가방(7 + 5 = 12)을 다른 친구에게 주면 두 사람 모두 12개의 사탕을 받게 되기 때문입니다.

해결 접근 방식

사탕 가방이 4개뿐이므로, 가능한 모든 나누기 조합을 직접 확인하는 것이 가장 간단하고 확실한 방법입니다. 4개의 가방을 두 그룹으로 나누는 경우는 크게 두 가지로 정리할 수 있습니다.

• 2 : 2로 나누기 — {a, b} vs {c, d}, {a, c} vs {b, d}, {a, d} vs {b, c}
• 1 : 3으로 나누기 — {d} vs {a, b, c}, {c} vs {a, b, d}, {b} vs {a, c, d}, {a} vs {b, c, d}

각 조합마다 두 그룹의 합이 서로 같은지 비교하고, 단 하나라도 일치하는 경우가 있다면 true를 반환하면 됩니다.

풀이 단계

다음 순서로 문제를 해결할 수 있습니다.

a := A[0]
b := A[1]
c := A[2]
d := A[3]
if (a + b) == (c + d) 또는 (a + c) == (b + d) 또는 (a + d) == (b + c)
   또는 (a + b + c) == d 또는 (a + b + d) == c
   또는 (a + c + d) == b 또는 (b + c + d) == a 라면:
    return true
그렇지 않으면:
    return false

예제 코드

아래 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

bool solve(vector<int> A) {
    int a = A[0];
    int b = A[1];
    int c = A[2];
    int d = A[3];
    if (a + b == c + d || a + c == b + d || a + d == b + c || a + b + c == d || a + b + d == c || a + c + d == b || b + c + d == a)
        return true;
    else
        return false;
}
int main() {
    vector<int> A = { 1, 7, 11, 5 };
    cout << solve(A) << endl;
}

입력

1, 7, 11, 5

출력

1

정리

이 풀이는 최대 7가지 조합만 비교하면 되므로 시간 복잡도는 O(1)로 상수 시간 안에 결과를 얻을 수 있습니다. 요소 개수가 적은 경우, 완전 탐색처럼 모든 경우를 명시적으로 확인하는 방법이 오히려 가독성과 안정성 면에서 유리할 수 있습니다.