백준 2629번 : 양팔저울

  와우... 이걸 푸는 다른 정석적인 풀이가 있을 것이지만... 나는 좀ㅋㅋㅋㅋ 편법적으로 풀었다. 만약 정석적인 풀이를 원하신다면 다른 블로그들을 참고하시길 바랍니다....ㅋㅋ

---

  풀이

  평범한 냅색문제처럼 접근했다. 일단 사용할 추의 무게들을 이용해 미리 만들 수 있는 무게를 저장해둔다. 만들 수 있는 무게를 계산하는 방법은 무게를 확인할 구슬이 양팔저울의 왼쪽에 있다고 가정했을 때 추를 오른쪽에 두면 그 만큼의 무게를 더하는 것이고 추를 왼쪽에 두면 그 만큼의 무게를 빼는 것이다. 그렇다면 dp를 다음과 같이 정의할 수 있다.

 

dp[i][j] : i번째 추까지 사용했을 때 j라는 무게를 측정할 수 있는지 없는지

 

  만약 추를 구슬의 반대쪽에만 둔다고 하면 무게를 계속 더하기만 하면 될 것이다. 그래서 1g과 4g이 있을 경우 잴 수 있는 무게는 1g, 4g, 5g이 될 것이다. 하지만 구슬이 있는 쪽에도 놓을 수 있기 때문에 1g을 구슬 쪽에 놓으므로서 01g, 3g, 4g, 5g까지 무게를 잴 수 있게 된다. 따라서 i번째 추를 사용하려고 할 때 i-1번째 추까지 사용했을 때 잴 수 있는 무게에서 i번째 추의 무게를 더하고 빼면서 dp를 확장시켜나가면 된다. i번째 추의 무게를 w라고 해보자.

 

dp[i-1][j]가 true라면

1. dp[i][j] = true

2. dp[i][j+w] = true

3. dp[i][j-w] = true

 

  이렇게 dp를 확장하면 j+w와 j-w가 배열의 범위 내에 있는지 한 번만 체크해주면 되기 때문에 쉽다! 하지만 큰 문제가 하나 있는데...

 

w가 더 클 경우 j-w가 음수가 된다!

 

하지만 음수를 버려서는 안된다. 1g, 4g이 있을 때 1g에 의해 dp[1][-1] = true, dp[1][1] = true여야 4g에 의해 dp[2][3] = true, dp[2][5] = true가 된다. 따라서 음수를 버리면 안되는데 배열을 음수를 받아들이지 못한다.

 

  편법

  그래서 나는 측정할 무게의 최댓값이 40000인 것을 이용해 0부터 80000까지의 배열을 만들었다. 초기값을 0이 아니라 40000에서 시작하고 측정할 무게도 40000을 더해줘서 보정해줬다. 즉 1g이 측정가능한지 판단할 때 40001g이 측정 가능한지를 판단하는 것이다. 이렇게 되면 다른 방법을 쓰지 않고 충분히 이중for문 만으로 해결이 가능하다.

 

 

#include <iostream>

using namespace std;

bool dp[31][80002];
int mid = 40000;

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    dp[0][mid] = true;
    
    for(int i = 1; i <= n; i++)
    {
        int w;
        cin >> w;
        for(int j = 0; j <= 80002; j++)
        {
            if(dp[i-1][j] == false) continue;
            dp[i][j] = true;
            if(j+w <= 80002) dp[i][j+w] = true;
            if(j-w >= 0) dp[i][j-w] = true;
        }
    }
    
    int m;
    cin >> m;
    
    for(int i = 0; i < m; i++)
    {
        int w;
        cin >> w;
        if(dp[n][w+mid]) cout << "Y ";
        else cout << "N ";
    }
    
    return 0;
}