[백준][C++] 2629: 양팔저울

 

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

2629번: 양팔저울

 

 

 

 

 

---

- 문제

 

  양팔저울과 n개의 추가 있고, 무게를 측정하고 싶은 m개의 구슬이 있을 때 추를 이용하여 구슬의 무게를 측정할 수 있는지 없는지 구하는 문제다.

 

 

---

- 해설

가방문제?와 비슷하게 풀 수 있을 것 같다.

 

결국 추 하나당 할 수 있는 행동은 3가지가 있다.

 

1. 추를 좌측 저울에 둔다.

 

2. 추를 두지 않는다.

 

3. 추를 우측 저울에 둔다.

 

 

위의 세 가지 행동을 모든 추가 한다면 그걸로 문제를 해결할 수 있다.

 

 

 

 

---

- 풀이

#include <iostream>
#include <vector>
using namespace std;

#define MAX 30


bool dp[MAX + 1][MAX * 500 + 1];
int weight, ball, temp;
vector<int> weights, balls;

void CheckWeights(int cnt, int result){
    if(cnt > weight){
        return;
    }
    if(dp[cnt][result] == true){
        return;
    }
    
    dp[cnt][result] = true;
    CheckWeights(cnt+1,result+weights[cnt]);
    CheckWeights(cnt+1,result);
    CheckWeights(cnt+1,abs(result-weights[cnt]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> weight;
    for(int i = 0; i < weight; i++){
        cin >> temp;
        weights.push_back(temp);
    }
    
    CheckWeights(0,0);
    
    cin >> ball;
    for(int i = 0; i < ball; i++){
        cin >> temp;
        balls.push_back(temp);
    }
    
    for(auto i : balls){
        if(i > MAX * 500){
            cout << "N ";
        }
        else if(dp[weight][i]){
            cout << "Y ";
        }
        else{
            cout << "N ";
        }
    }
    
    
    return 0;
}

 

 

---

- 새롭게 알게 된 점