[BOJ/백준][Silver1] 17610 : 양팔저울 (C++)

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

17610번: 양팔저울

 

 

[난이도] Silver1
[유형] 브루트포스

[풀이]
추의 무게를 더하거나 빼서 만들 수 있는 모든 무게를 구해주면
이 무게들이 추를 이용해 만들 수 있는 무게들입니다.

 

#include <cstdio>
int k,v[14],a[3000000],sum,ans;
void sol(int n,int cur){
    if(cur>=1) {
        if(!a[cur]) ans++;
        a[cur]=1;
    }
    if(n==k) return;
    sol(n+1,cur+v[n]);
    sol(n+1,cur-v[n]);
    sol(n+1,cur);
}
int main(){
    scanf("%d",&k);
    for(int i=0;i<k;i++){
        scanf("%d",&v[i]);
        sum+=v[i];
    }
    sol(0,0);
    printf("%d",sum-ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/17610.cpp