[BOJ] 백준 2629번 - 양팔저울 풀이

| |
백준 온라인 저지 백준 2629번 - 양팔저울 C++ 풀이


문제

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

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

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

1

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

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

2


입력

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


출력

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


풀이

완전탐색으로 해결하기엔 경우의 수가 최대 3^30 * 7 이 나오기 때문에 불가능하다. 따라서 이 문제는 배낭 문제로 접근하여 DP를 사용해야 한다.

추 하나에 따라서 다음과 같이 3가지 경우의 수로 나눌 수 있다.

  • 추를 구슬이 놓인 저울에 놓는다.
  • 추를 구슬이 놓이지 않은 저울에 놓는다.
  • 추를 사용하지 않는다.

그리고 다음과 같은 조건이 성립할 때 구슬의 무게를 측정할 수 있다.

양쪽 저울의 무게가 같다

따라서 위 3가지 경우를 탐색하며 모든 추에 대해 탐색했을 때 양쪽 저울의 무게가 같아지는 경우의 수가 하나라도 있을 시 구슬의 무게를 측정할 수 있다.

양쪽 저울의 무게가 같음은 다음으로 판단할 것이다.

구슬이 있는 저울의 무게 - 반대편 저울의 무게 = 0

이 때 저울 무게의 차가 음수가 되는 경우가 생기기 때문에 그대로 DP를 적용시키긴 힘들다. 그런데 추의 최대 개수는 30, 추 하나의 최대 무게는 500 이므로 두 저울 무게의 차는 아무리 작아지더라도 -15000 이하로 내려가지 않는다. 따라서 매 계산마다 DP배열의 인덱스에 +15000을 해주면 음수가 되는 상황을 막을 수 있다.

또 하나 관찰할 수 있는건 구슬의 최대 무게가 40000까지 주어진다는 것이다. 앞에서 살펴봤듯이 모든 추의 무게 합이 최대 15000을 넘길 수 없으므로 구슬의 무게로 15000이상이 주어질 경우 무조건 불가능함을 알 수 있다. 이를 미리 전처리하면 실행 시간을 단축시킬 수 있다.

아래는 재귀와 메모이제이션을 통해 문제를 해결한 코드이다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N,M;
vector<int> chu, bid;
long long cache[30][45001];

long long solve(int n, int sum){
   if(n==N) return sum==0 ? 1 : 0; // 양쪽 무게가 같을 경우 1

   long long& ret=cache[n][sum+15000]; // 음수 방지
   if(ret!=-1) return ret;

   ret=0;
   ret+=solve(n+1,sum); // 추를 사용하지 않음
   ret+=solve(n+1,sum+chu[n]); // 추를 구슬이 있는 저울에
   ret+=solve(n+1,sum-chu[n]); // 추를 구슬이 없는 저울에

   return ret;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   cin>>N;
   chu.resize(N);
   for(int& i:chu) cin>>i;

   cin>>M;
   bid.resize(M);
   for(int& i:bid) cin>>i;

   for(int i:bid){
      if(i>15000){ // 무게가 15000 초과일 시 무조건 불가능
         cout<<"N ";
         continue;
      }
      memset(cache,-1,sizeof(cache));
      cout<<(solve(0,i)>0LL?"Y ":"N "); // 1번이라도 같아지면 YES
   }

   return 0;
}
0%