Baekjoon 2629. 양팔저울 / Python

2629. 양팔저울

난이도 : 골드 3
소요 시간 : 25분
날짜 : 2025.01.09
언어 : 파이썬
알고리즘 유형 : dp, 배낭문제(napsack)

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 양팔저울이 있고, 가진 추의 무게들이 주어진다.
2. 무게를 확인할 구슬들이 주어진다.
3. 구슬의 무게를 확인가능한지 여부를 출력한다.

2. 해결 방식

1. dp[i][j] : i개의 구슬을 사용, j의 무게를 잴수 있는 지 여부
2. dp의 크기 $x*y$ : x는 개수이므로 n$ + 1$, y는 무게이므로 구슬들의 최대 무게인 sum(weights)
3. 재귀함수 구현 sol(cnt, cost)
   • cnt : 현재 구슬의 인덱스, 방문한 구슬의 개수를 나타내기도 한다.
   • cost : 확인한 현재 무게
   • 종료조건 : cnt가 n 인 경우 종료, dp[cnt][cost]가 True인 경우(이미 방문) 종료
   • 방문처리를 한 후에,
   • sol(cnt + 1, cost + w), sol(cnt + 1, cost - w), sol(cnt + 1, cost)를 재귀로 돈다.
   • 순서대로, 무거운쪽에 추를 얹는 것, 가벼운 쪽에 추를 얹는 것, 이번 추를 사용하지 않는 것,

시간복잡도 : 구슬의 개수 최대 7개이므로, 최악의 경우 $3^7 = 2187$ 이다.

3. 정답 코드

import sys;input = sys.stdin.readline

n = int(input())    # 30이하, 추의 개수
weights = list(map(int, input().split()))   # 무게 순 추 무게들
max_weight = sum(weights)

m = int(input())   # 확인하고픈 구슬 개수
marbles = list(map(int, input().split()))   # 무게 순 구슬들

dp = [[0] * (max_weight + 1) for _ in range(n + 1)] # dp[i][j] : i개, 무게j
res = ''

def sol(cnt=0, cost=0):
    if dp[cnt][cost] == 1:return
    dp[cnt][cost] = 1
    if cnt == n:return

    sol(cnt+1, cost + weights[cnt])
    sol(cnt+1, cost)
    sol(cnt+1, abs(cost - weights[cnt]))
sol()

for marble in marbles:
    if marble > max_weight:res+='N '
    if dp[n][marble]:res+='Y '
    else:res+='N '
print(res)