[ BOJ 백준 2629번 - 양팔저울 ] 해설 및 코드

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

2629번: 양팔저울

목적

주어진 추 N개를 이용하여 측정할 수 있는 모든 무게를 구한다.

 

접근법

1. a[i]는 i 번째 추의 무게이고, s[i]는 1~i번째 추를 사용하여 만들 수 있는 무게라고 가정할 때, s[i]를 다음과 같이 나타낼 수 있다.

- s[i-1]

- s[i-1] + a[i]

- abs(s[i-1] - a[i])

즉, 이전까지 만든 무게에 현재 idx에 해당하는 추의 무게를 가할지, 감할지, 아무작업도 안 할지의 세가지로 측정가능한 무게를 만들어낼 수 있다.

 

2. 위의 점화식을 사용하여 재귀적으로 알고리즘을 구현하고, 중복 연산을 막기 위한 작업도 해준다.

 

#include<iostream>
#include<cmath>
using namespace std;
 
int n,weights[31];
bool measurable[15001]={}, measured[31][15001]={};
 
void measure(int i,int weight){
    if(i>n) return;
    if(measured[i][weight])return;
    measured[i][weight]=true;
    measurable[weight]=true;
    
    measure(i+1,weight);
    measure(i+1,weight+weights[i]);
    measure(i+1,abs(weight-weights[i]));
}
 
int main(){
    cin>>n;for(int i=0;i<n;++i)cin>>weights[i];
    measure(0,0);
    
    int t;cin>>t;
    while(t--){
        int ball;cin>>ball;
        if(ball<=15000&&measurable[ball])cout<<'Y';
        else cout<<'N';
        cout<<' ';
    }
}