KOI 2019 1차 중등부 1번 / 양팔저울 - 17610

#include <iostream>
#include <vector>
using namespace std;
 
int N;
int arr[13];
vector<bool> flag;
int sum;
 
void slv(int idx, int cs, int num) {
    if(idx == N) {
        if(num >= 1 && !flag[num]) {
            flag[num] = true;
            --sum;
        }
        return;
    }
 
    if(cs == 1) num += arr[idx];
    else if(cs == 2) num -= arr[idx];
 
    slv(idx+1, 0, num);
    slv(idx+1, 1, num);
    slv(idx+1, 2, num);
}
 
int main() {
    cin >> N;
    sum = 0;
    for(int i= 0; i<N; ++i) {
        cin >> arr[i];
        sum += arr[i];
    }
    flag = vector<bool>(sum+1, false);
    slv(0, 0, 0);
    slv(0, 1, 0);
    slv(0, 2, 0);
    cout << sum;
}

 

 

 

 

 

https://www.acmicpc.net/problem/17610

17610번: 양팔저울

 

 

 

 

 

양팔저울

각각의 저울을 더한다, 뺀다, 아무것도안한다 3가지 동작에 대해 모든 경우에 수를 따져주어 만들 수 있는 수의 개수를 세면 정답을 구할 수 있습니다.

3^13은 백만임으로 완전탐색으로도 시간안에 해결할 수 있습니다.