[백준] [C++] 양팔저울 (dp)

1. 문제

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

2629번: 양팔저울

 

2. 완전탐색 

이 문제에서 구슬을 비교하는 추의 개수와 종류는 전부 동일하다.

 

따라서 주어진 추를 사용해서 만들 수 있는 모든 경우의 무게를 만들고나면

 

구슬의 무게를 확인할 수 있다.

 

추는 한번만 사용할 수 있으므로

 

각각의 추에대해서  3가지 선택을 해야한다

 

1. 추를 구슬쪽에 올릴 경우 (w - weight[idx])

2. 추를 올리지 않는 경우 (w)

3. 추를 반대편에 올릴 경우 (w + weight[idx])

 

이를 완전 탐색방법으로 나타낸 코드는 다음과 같다.

bool cache[80001];
 
void initialize(vector<int>& weight, int idx, int w) {
    cache[w + 40000]= true;
 
    if(idx == weight.size())
        return;
 
    initialize(weight, idx+1,  w - weight[idx]);
    initialize(weight, idx+1,  w);
    initialize(weight, idx+1,  w + weight[idx]);
}

3.  동적계획법-메모이제이션

위의 중복계산을 줄일 수 있는 방법은

 

중복문제를 만들어내는 변수를 찾고 메모하는 메모이제이션 기법을 사용하는것이다.

 

위 문제에서는 추의 인덱스와 지금까지 만든 무게에 의해 중복문제가 만들어지므로

 

아래 코드와 같이 인덱스와 무게를 인덱스로 놓고 기록을하면

 

위의 예시같은 경우들은 계산을 단 한번만 하게된다.

 

 

그리고 만들어진 모든 무게는 2번째 추를 올리지 않는 선택으로 인해

모두  마지막 열에 저장된다.

cache[marble + MAX][weight.size()] 

 

#include <iostream>
#include <vector>
#include <numeric>
 
using namespace std;
 
const int MAX = 30*500;
bool cache[2*MAX + 1][31];
 
void initialize(vector<int>& weight, int idx, int w) {
 
    if(cache[w + MAX][idx]) {
        return;
    }
    
    cache[w + MAX][idx] = true;
    if(idx == weight.size())
        return;
    
    initialize(weight, idx+1,  w - weight[idx]);
    initialize(weight, idx+1,  w);
    initialize(weight, idx+1,  w + weight[idx]);
}
 
int main() {
    int n, m;
    cin>>n;
 
    vector<int> weight(n);
    for(int i = 0; i < n ; i++) {
        cin>>weight[i];
    }
    initialize(weight, 0, 0);
 
    cin>>m;
    
    for(int i = 0; i < m; i++) {
        int marble;
        cin>>marble;
        if(marble > MAX) {
            cout<<"N ";
        }
        else if(cache[marble + MAX][weight.size()]) {
            cout<<"Y ";    
        }
        else {
            cout<<"N ";
        }
    }
    cout<<"\n";
}