[KOI 2019 1차대회][중등부1번] 양팔저울

문제:

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

17610번: 양팔저울

 

문제해석:

위 그림과 같이 왼쪽 저울에 물을 담기위한 빈그릇을 고정한다고 가정해보자.

자 우리는 한개의 추를 가지고 3가지 행동을 할수있다.

 

1. 추를 오른쪽에 올린다 :: 이 경우 빈그릇에 무게는 추의 무게만큼 증가한다.

2. 추를 왼쪽에 올린다 :: 이 경우 빈그릇에 무게는 추의 무게만큼 감소한다.

3. 추를 어느저울에도 올리지 않는다 :: 이 경우 빈그릇에 무게의 변화가 없다.

 

추의 최대갯수가 13개 이기 때문에 [worst-case] O(3^13) = 1,594,323 시간제한 1초안에 충분히 연산가능하다.

 

0-based 추의 무게를 배열에 저장을하고 재귀 함수를 통해 k개의 추를 통해 얻을수있는 빈그릇에 무게를 구할수가있다.

[0...k-1]번째 추를 순차적으로 3가지 행동중 한개를 선택하다 추를 나타내는 index가 k가 되는 순간 [0...k-1] 즉, k개의 추를 통해 얻은 무게를 표현가능하다고 표시해주면된다. 단 주의해야할 점은 음수가 나올수 있다는 점이다.

 

또 이문제에서 표현할수있는 최대 무게는 200,000(추의 최대무게) * 13(추의 최대갯수) = 2,600,000 이다.

 

시간복잡도 분석:

n개의 추 각각이 3개의 행동을 할수있으니 O(3^n)

 

코드:

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAX_G = 2e5;
int k, arr[13];
bool ok[MAX_G * 13 + 1]; // [0...MAX_S*13]
void solve(int idx, int weight)
{
    if(idx == k) {
        if(weight > 0) ok[weight] = true;
        return;
    }
    solve(idx+1,weight + arr[idx]);
    solve(idx+1,weight - arr[idx]);
    solve(idx+1,weight);
}
 
int main()
{
    cin >> k;
    int S = 0, cnt = 0;
    for(int i=0; i<k; i++){
        cin >> arr[i];
        S += arr[i];
    }
    solve(0,0);
    for(int i=1; i<=S; i++){
        if(!ok[i]) cnt++;
    }
    cout << cnt <<'\n';
    return 0;
}