BOJ 2629 양팔저울

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

2629번: 양팔저울

 

0. 문제 개요

추 여러 개와 Target이 주어진다. 추를 조합하여 Target 무게를 만들 수 있는지 확인하는 문제.

 

 

 

 

1. 문제 해결 아이디어

(1) i번째 추까지 이용하여 무게를 조합하여 그 무게를 set[i] 배열에 집어넣는다. (중복성을 제거하기 위해 set을 이용)

(2) n번째 추까지 탐색했을 때 해당 set[n]배열에 target값이 존재하는지 확인한다.

 

 

 

무게를 조합하는 경우의 수는 다음과 같다.

1) 이전까지 무게 + 현재 추

 

2) abs(이전까지 무게 - 현재 추)                   //절대값 차를 이용해 target이 만들어질 수도 있으므로.

-> 이전까지 무게 + target = 현재 추  -> target = abs(현재 추-이전까지 무게)

                                                                            

3) 이전까지 무게 그대로 유지          // 현재 추를 사용하지 않는다.

 

이를 코드로 구현하면 아래와 같다.

 

 

 

 

2. 코드

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
using namespace std;
int n, tN;
int a[35];
set<int > set_arr[35];
int flag;
void solve(int pos,int target) {
    
    if (pos == n) {                                 //종결 조건 : 모든 추를 다 탐색했다.
        for (int x : set_arr[pos-1]) {
            if (x == target) {                     //조합한 추 무게중 TARGET이 있다면
                flag = 1;                         //FLAG를 설정한다.
            }
        }
        return;
    }
    set<int> s;
    for (int x : set_arr[pos - 1]) {         //이전까지 추로 만든 무게들에 대해
        set_arr[pos].insert(x + a[pos]);        //현재 추를 더한 무게
        set_arr[pos].insert(abs(x - a[pos]));    //현재 추를 뺀 무게
       set_arr[pos].insert(x);                     //현재 추를 사용하지 않는 무게
    }
    solve(pos + 1, target);                        //다음 추를 탐색한다.
 
}
 
int main() {
 
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0;i < n;i++) {
        cin >> a[i];
    }
    set_arr[0].insert(0);                        //처음 추를 사용하지 않았을 때 무게(==0) 삽입
    set_arr[0].insert(a[0]);                    //처음 추의 무게 삽입
    cin >> tN;
    int t;
    for (int i = 0;i < tN;i++) {
        cin >> t;
        flag = 0;
        solve(1, t);                            //두번째 추부터 탐색.
        if (flag == 1) {
            cout << 'Y' << ' ';
        }
        else
            cout << 'N' << ' ';
    }
    
 
    return 0;
}

3. 나가며...

dp 2차원 배열을 이용해서 풀 수도 있다!

모든 무게의 합을 dp 배열에 저장해 놓는 식으로!