2692. 양팔저울

2629번: 양팔저울

---

추를 적절히 이용해서 주어진 무게를 잴 수 있을까?

 

브루트 포스를 이용하여 가장 쉽게 문제를 해결할 수 있다. 그러나 이 문제에서는 추가 최대 30개이므로 2^30개의 가능성을 모두 탐색하다간 시간 초과를 받을 것이다.

 

잠시 생각해 보자. 왼쪽과 오른쪽에 추와 물체를 적당히 올려서 물체의 무게를 재고 싶다. 이 상황을 간단한 수식으로 표현하면 다음과 같다. 물체는 왼쪽에만 올린다고 가정하자.

왼쪽 추의 무게의 합 + 물체의 무게 = 오른쪽 추의 무게의 합

추를 적절히 조합해서 물체의 무게가 될 수 있는 수를 찾으면 된다!

 

여기까지 읽은 후에 문제를 직접 해결해 보고, 그래도 어렵다면 다음을 읽어 보자.

다이나믹 프로그래밍으로 문제를 해결할 수 있다. 첫 번째 입력되는 추를 1번 추라고 가정하며, 다음의 dp 배열을 생각하자.

 

dp[i][j] = 1~i번 추를 이용하여 무게 j를 만들 수 있다면 true, 아니라면 false

 

이제 (i+1)번 추를 이용해 보자. 물체는 왼쪽에만 놓고, dp[i-1][j] = true라고 가정하자. 현재 추의 무게를 cur이라고 할 때 수평을 맞추는 물체의 무게 w는 다음과 같다.

 

0) cur = cur

    - 왼쪽에는 무게가 cur인 물체만, 오른쪽에는 (i+1)번 추 하나만 올라가 있다.

    - w = cur

1) j = j 

    - (i+1)번 추를 사용하지 않고 1~i번 추만 사용하는 경우

    - w = j

2) (j - cur) + cur = j

    - 왼쪽에 물체와 (i+1)번 추가 있고, 오른쪽에는 무게가 j인 추의 집합이 있다.

    - w = (j - cur)

3) (j + cur) = j + cur

    - 왼쪽에는 무게가 (j + cur)인 물체만, 오른쪽에는 추만 올라가 있다.

    - w = j + cur

4) w + cur = j

    - 왼쪽에는 물체와 (i+1)번 추가, 오른쪽에는 무게가 j인 추의 집합이 있다.

    - w = (cur - j)

 

뭔 소린지 헷갈린다면 각 상황을 그림으로 그려 보자. 물체, (i+1)번 추, 무게가 j인 추의 집합을 그려 보면 평형을 맞추는 그림이 보일 것이다.

 

이제 위의 식에 따라 dp 배열을 채우면 된다.

다섯 가지 경우의 w에 대해 dp[i-1][w]가 true라면 dp[i][j]도 true다.

컴퓨터 그래픽을 잘 다룬다면 직접 그림을 그렸을 텐데.. 그림 연습도 해야 하나?

---

코로나 언제쯤 잡히니.. ㅠㅠ