[C++]백준 - 2629번 문제

2629번: 양팔저울 (acmicpc.net)

2629번: 양팔저울

 

2629번 : 양팔저울

---

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 1> 구슬이 3g인지 확인하는 방법 (1은 1g인 추, 4는 4g인 추, ●은 무게를 확인할 구슬)

 

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

<그림 2> 구슬이 5g인지 확인하는 방법

 

입력

---

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

 

 

출력

---

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

 

 

 

---

 

생각해 볼 점

---

동적 프로그래밍 문제입니다.

 

냅색 알고리즘과 유사한 부분이 있습니다.

 

우선, Bool 타입의 이차원 배열 DP를 만들어서 다음과 같이 정의 합니다.

 

DP[index][weight]

 

index = index까지의 추를 사용할 때

weight = weight의 무게를 만들 수 있는가?

 

예를 들어 DP[3][5] = 1~3번째 추를 사용하여 5g을 만들 수 있는지의 여부

 

주의할 점은, 좌측에도 무게를 달 수 있으므로, 여러 추를 사용한 덧셈 및 뺄셈까지 고려해야합니다.

 

따라서, 다음과 같이 진행합니다.

 

예를들어, 추 5개 {2, 3, 3, 3, 3}을 받았을 때

 

DP[0] = 추를 한개도 사용하지 않으므로 모두 0입니다.

DP[1] = 1번째 추(2g)을 추가합니다. DP[1][2] = 1입니다.

DP[2] = 2번째 추(3g)을 추가합니다. DP[2][3] = 1입니다.

           DP[2]를 탐색하여 1인 항목이 있으면 다음을 진행합니다.

           1. DP[2]의 1인 항목의 무게 (2g) = 1 -> DP[3][2] = 1

           2. 해당 항목의 무게(2g) + 이번 추의 무게 -> DP[3][5] = 1

           3. (해당 항목의 무게(2g) - 이번 추의 무게)의 절댓값 -> DP[3][1] = 1

 

위의 과정을 반복하여

DP[모든 추의 갯수][확인하고 싶은 무게] == 1이면, Y 아니면 N을 출력합니다.

 

코드

---

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

int main() 
{
    int w, m;
    cin >> w;
    
    int *weight = new int[w + 1];
    int max_weight = 0;
    for(int i = 1; i < w + 1; i++)
    {
        cin >> weight[i];
        max_weight += weight[i];
    }
    cin >> m;
    
    
    for(int i = 0; i < m; i++)
    {
        int marble;
        cin >> marble;
        
        bool **dp = new bool*[w + 1];   //i까지의 추로 해당 무게를 만들 수 있는가?
        dp[0] = new bool[max_weight + 1];
        fill_n(dp[0], max_weight + 1, false);
        
        //DP 알고리즘
        for(int j = 1; j < w + 1; j++)
        {
            dp[j] = new bool[max_weight + 1];
            fill_n(dp[j], max_weight, false);
            dp[j][weight[j]] = true;    //i번 째 추 = true
            
            //i-1번 째에 잴수 있었던 무게에서 i번째 추를 추가함
            for(int k = 0; k < max_weight + 1; k++)
            {
                if(dp[j-1][k])
                {
                    dp[j][k] = true;
                    int plus = k + weight[j];
                    int minus = abs(k - weight[j]);
                    
                    if(plus <= max_weight) dp[j][plus] = true;
                    if(minus <= max_weight) dp[j][minus] = true;
                }
            }
        }
        
        //출력
        if(dp[w][marble]) cout << "Y\n";
        else cout << "N\n";

        for(int j = 0; j < w + 1; j++) delete[] dp[j];
        delete[] dp;
    }
    delete[] weight;

	return 0;
}

 

그 외

---