[백준] 2629번 : 양팔저울

2629번: 양팔저울

2629번: 양팔저울

📄 문제개요

• 양팔 저울과 몇개의 추가 주어졌을때, 이를 이용하여 입력으로 주어진 무게의 구슬을 확인 할 수 있는지 결정하고자 한다.
• 제한된 추의 개수가 주어지고 ( 30개 이하 ), 추의 무게는 500g 이하이며, 구슬의 개수는 7개 이하이다.
• 각 구슬의 무게에 대하여 확인이 가능하면 Y 아니면 N을 출력한다.
• 양팔 저울에는 추를 둘다 놓을 수 있다.

🤔 문제분석

다이나믹 프로그래밍

• 현재의 추를 왼쪽으로 둔경우와, 오른쪽에 둔 경우 모두 갱신한다.
• 왼쪽에 둔 경우는 오른쪽의 무게가 자기자신 - 오른쪽의 무게 ≥ 0 이어야 한다.
• 1,4 추가 있다면, 추를 무거운 순으로 방문처리 한다.
• v[추의무게]
  1. v[4] = True
  2. v[5], v[3] = True ( 추를 오른쪽에 둔경우, 추를 왼쪽에 둔경우 )
• 구슬은 무게 4,5,3 측정이 가능하다.
• 시간복잡도 : 추의 최대 무게 30 * 500 = 15000, 추의 개수 30, O(30 * 15000) = O(450,000)

완전탐색 접근

• 추의 개수가 30개 이하로, 충분히 작기때문에 모든 경우의 수를 생성하여 만들어본다.
• 왼쪽영역의추, 오른쪽 영역의 추를 나누어본다. (0, 30), (1,29), (2,28) … (15,15) : 경우의 수 : 625개
• 추를 놓아서 놓을 수 있는 경우를 업데이트 한다. 30 * 625 = 20000
• 메모리 복잡도가 너무 높고 시간복잡도도 너무 높다.

📝 의사코드

• 추의 리스트들을 순회한다. ( 이미 추는 오름차순 정렬 되어 있음 )
  1. 자기자신의 추를 무게를 잴 수 있다고 표기한다.
  2. 15000무게부터 자기자신무게까지 반복문을 순회하면서, (현재무게)가 이미 방문한 무게라면, (현재무게 - 자기자신의 무게 ), (현재무게 + 자기자신의 무게) 를 무게를 잴 수 있다고 표기한다.
     1. 예를들어 직전의 무게가 4에서 방문처리를하고, 1의 무게가 5와 3의 무게를 만들 수 있다고 업데이트 한다.
  3. 반복문이 끝나면 구슬의 무게를 query로 이용해 O(1)으로 구슬의 무게를 잴 수 있는지 확인한다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
chu = list(map(int, input().split()))

M = int(input())
gu = list(map(int, input().split()))

v = [False for _ in range(40001)]

#chu.sort(reverse=True)

for c in chu:
    # 오른쪽, 왼쪽에 둘 수 있음을 표기한다.
    update = []
    for w in range(1, len(v)- c):
        if v[w]:
            update.append(w+c)
            update.append(abs(w-c))
    
    # 자기자신을 무게를 잴 수 있다고 표기한다.
    v[c] = True
    for u in update:
        v[u] = True

for g in gu:
    if v[g]:
        print('Y', end= ' ')
    else:
        print('N', end= ' ')
print()

🎯 피드백 및 개선사항

• 추를 내림차순으로 정렬해서 문제를 풀려고 접근을 하였습니다.
• 예외의 상황인 를 해결하지 못하였습니다. 6은 (7+8) - 9 로 나타낼 수 있습니다.
• 9는 왼쪽 7,8은 오른쪽에 둔다.

3
7 8 9
1
6

❓다른사람은 어떻게 풀었을까?

• 집합 자료구조를 활용하여 문제를 해결한 사람을 찾을 수 있습니다.
• 비슷한 원리로 문제를 해결하였으나, 메모리 복잡도 부분에서 좀더 우수한 성능 갖습니다.
• v테이블을 40000 을 생성하였고, 아래의 문제는 문제의 조건에 따라서 동적으로 생성됩니다.

num_weight = int(input())
weights = [0] + list(map(int, input().split()))
num_gem = int(input())
gems = list(map(int, input().split()))

dp = set()

for weight in weights:
    new = set({weight})

    for num in dp:
        new.add(abs(num-weight))
        new.add(num+weight)
    
    dp = dp.union(new)

for gem in gems:
    print("Y" if gem in dp else "N", end=" ")
print()