(2629) 양팔저울

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

단계별로 풀어보기

31단계(동적 계획법 2) 4번째

 

 

 

배낭 문제랑 똑같은데, 물건을 넣기만 할 수 있었던 가방 문제와 달리 양팔저울의 왼쪽 오른쪽 전부 추를 놓을 수 있다.

따라서 추를 더하는 경우 말고 빼는 경우도 계산해야 한다.

또한 계산 중간에 왼쪽이 더 무거운 경우가 생길수도 있으므로 이를 고려하여 범위를 잡아야 한다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n;
  
  vector<bool> dp(55001);
  
  dp[15000]= true;
  
  while(n--){
    int w;
    
    cin >> w;
    
    vector<int> res;
    
    for(int i=0;i<=55000;i++){
      if(dp[i])  res.push_back(i);
    }
    
    for(int x:res){
      if(x-w>=0)  dp[x-w]= true;
      if(x+w<=55000)  dp[x+w]= true;
    }
  }
  
  cin >> m;
  
  while(m--){
    int w;
    
    cin >> w;
    
    cout << (dp[w+15000] ? "Y " : "N ");
  }
  
  return 0;
}