[AlgorithmSolving][DP] JUNGOL_1352: 양팔 저울

1. 문제 내용

• 문제:

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

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

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

  

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

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

  

• 입력:

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

• 출력:

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

2. 문제 유형 파악

이 문제는 주어진 추들을 조합하여 특정 무게를 측정할 수 있는지 판별하는 문제로, 전형적인 배낭 문제의 변형이자 DP 문제입니다.

• 시간 복잡도 분석(완전 탐색의 한계):

  주어진 추의 개수 N은 최대 30개입니다. 하나의 추를 다룰 때 우리가 할 수 있는 행동은 3가지(안쓴다, 왼쪽에 놓는다, 오른쪽에 놓는다)이므로, 모든 경우의 수를 탐색하는 브루트 포스 방식을 사용하면 $O(3^{30})$ 으로 시간 초과 판정을 받게됩니다.

• DP의 적용 타당성 (부분 문제의 중복)

  추의 최대 개수는 30개, 각 추의 최대 무게는 500g이므로, 추를 모두 더해도 만들 수 있는 최대 무게는 15,000g에 불과합니다. 즉 추를 조합하다 보면 “같은 무게”가 만들어지는 경우가 무수히 많이 중복됩니다. 따라서 이전에 만들어둔 무게 상태를 기억해 두고 다음 추를 올릴 때 활용하는 DP가 완벽한 해결책이 됩니다.

3. 문제를 풀기 위한 핵심 아이디어

이 문제를 관통하는 핵심은 양팔 저울의 특성을 수학적인 덧셈과 뺄셈으로 치환하여 상태를 전이 시키는 것입니다.

1. 하나의 추가 가질 수 있는 3가지 상태

   1. 추를 사용하지 않는다.
   • 기존에 측정 가능했던 무게 w를 그대로 유지합니다 -> w
   1. 추를 구슬의 반대편 저울에 올린다(무게 더하기)
   • 저울이 더 무거운 구슬을 감당할 수 있게 되므로, 측정 가능한 무게가 늘어납니다. -> w+k
   1. 추를 구슬과 같은 편 저울에 올린다 (무게 빼기)
   • 내가 가진 기존의 무게 w에서 현재 추의 무게 k마늠을 뺀 무게의 구슬을 측정할 수 있게 됩니다.

   • 이때 무게는 음수가 될 수 없으므로 절대값을 씌워줍니다. ->

     w-k

2. 2차원 DP 테이블의 정의

위의 3가지 상태를 기록하기 위해 다음과 같이 DP배열을 정의합니다.

- DP[i][w]: i번째 추까지 고려했을 때, 무게 w를 측정할 수 있는가(Boolean 또는 1/0)
- 배열의 크기: 행은 추의 개수(최대 30), 열은 가능한 최대 무게(15,000)로 설정합니다.

1. 점화식

이전 단계(i-1번재 추까지 확인)에서 무게 w를 만들 수 있었다면(즉, $DP[i-1][w]$가 참이라면), i번째 추(무게 weight[i])를 사용하여 다음 세 가지 상태를 True로 갱신합니다.

\(DP[i][w] = \text{True}\)\(DP[i][w + weight[i]] = \text{True}\)\(DP[i][\vert{}w - weight[i]\vert{}] = \text{True}\)

1. 엣지 케이스 처리 (불가능한 무게의 조기 차단)

문제에서 주어지는 확인용 구슬의 무게는 최대 40,000g까지 들어올 수 있습니다. 하지만 우리가 가진 모든 추를 다 더해도 만들 수 있는 최대 무게는 15,000g(30개 x 500g)입니다.
따라서 구슬의 무게가 전체 추의 총합보다 무겁게 들어온다면, DP 테이블을 확인할 필요도 없이 즉시 불가능으로 판정하는 예외 처리를 추가하면 실행 시간을 더욱 최적화할 수 있습니다.

4. 코드

해당 문제의 코드는 다음과 같습니다.

import sys

def solve():
    input = sys.stdin.readline

    n = int(input())
    weights = list(map(int, input().split()))

    m = int(input())
    check_weights = list(map(int, input().split()))

    sum_weight = sum(weights)
    dp = [False] * (sum_weight+1)
    dp[0] = True

    for weight in weights:
        next_dp = [False] * (sum_weight+1)

        for w in range(sum_weight+1):
            if dp[w]:
                next_dp[w] = True
                next_dp[w+weight] = True
                next_dp[abs(w-weight)] = True

        dp = next_dp

    for i in range(m):
        w = check_weights[i]

        if w <= sum_weight and dp[w]:
            print("Y", end=" ")
        else:
            print("N", end=" ")

solve()