[C++] [CSES] Apple Division (Introductory Problems)

CSES의 열 여섯번째 문제입니다.

숫자들로 이루어진 배열을 두 부분으로 나누어 두 합의 차의 최솟값을 구하는 문제입니다.

Subset Sum 의 간단한 응용입니다. 재귀를 이용한 완전탐색을 사용했습니다.

 

Task

There are n apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Input

The first input line has an integer n: the number of apples.

The next line has n integers p1,p2,…,pn: the weight of each apple.

Output

Print one integer: the minimum difference between the weights of the groups.

Constraints

• 1≤n≤20
• 1≤pi≤1e9

Example

Input:
5
3 2 7 4 1

Output:
1

Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).

 

Code

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

ll n, ar[22], summ, mn = 1e18;

void go(ll cnt, ll cur){
    if (cnt == n){
        mn = min(mn, abs(summ - cur * 2));
        return;
    }
    go(cnt + 1, cur);
    go(cnt + 1, cur + ar[cnt]);
}
int main(){
    cin >> n;
    for (int i=0;i<n;i++){
        cin >> ar[i];
        summ += ar[i];
    }
    go(0, 0);
    cout << mn;
}

생각해야 하는 것

• n 이 20 이하임을 보고 2^n도 수월하게 통과할 수 있음을 알아냈습니다.
• 배열을 순회하면서 해당 인덱스의 값을 넣거나 넣지 않고 다음 인덱스로 이동합니다.
• 인덱스가 배열의 끝이면 자신이 담고 있는 숫자(cur) 와 담지 않았던 숫자(summ - cur)을 비교합니다. 여기서 절댓값 함수를 사용했습니다.
• int 범위를 넘어갈 수 있습니다.