[다이나믹 프로그래밍] ★★ 2629번 - 양팔 저울

[백준] 2629번 - 양팔 저울

(한줄평) 생각보다 머리가 복잡했던 문제.. 점화식을 만들기가 어려웠다.. 무조건 복습필수다

풀이 시간: 90분 이내

 

1) 문제 해결 아이디어

추의 개수 n(30 이하), n개의 추의 무게(500이하의 자연수)가 오름차순으로 주어지고

구슬의 개수 m(7이하), m개의 구슬의 무게(40000 이하의 자연수)가 주어진다.

양팔 저울에 추를 사용하여(올리거나 올리지 않을 수 있음) 주어진 m개의 각 구슬의 무게를 확인할 수 있는지 여부를 구하는 문제다.

 

각 추를 사용할 때 3가지 경우의 수가 있다.

즉, 추의 개수가 n이면 추를 이용하여 구할 수 있는 모든 경우의 수는 3**n이 된다.

n의 값이 최대 30이므로 단순하게 완전 탐색을 한다면 이 문제는 시간초과로 풀 수 없게된다.

그러므로 중복된 것은 계산하지 않도록 하는게 이 문제의 핵심이다.

각 추에 대해 동일한 3가지 경우를 반복하므로 재귀를 이용하여 푼다. 다만 2차원 배열의 dp를 만들어서 사용한 추의 개수에 대해 만들 수 있는 무게를 True/False로 체크한다.

여기서 사용이라함은 추를 정말 올렸다는 것이 아니라 단순하게 추를 올리지 않을지, 왼쪽/오른쪽에 올릴지를 검사했다는 의미다. 

예를 들어, 추 5개를 사용했다는 것은 실제로 모든 추 5개를 저울에 올렸다는 의미가 아니라 추 5개를 올릴지 말지 고려했다는 의미다.

 

<추를 사용하는 방법 3가지>

구슬의 무게는 항상 오른쪽 추들과 왼쪽 추들의 차이값이다. 

여기서 주의할 점은 두 쪽의 추들의 무게의 차이가 음수가 되면 안되므로 절댓값을 꼭 취해야한다는 점이다.

 

Q. 3가지 경우에서 weights의 인덱스가 (num - 1)인 이유는?

여기서 현재 올릴지 말지 고려하는 추는 num번째 추이므로 weights[num]이어야한다고 생각할 수 있다. 

하지만 2차원 배열 d를 행(30 + 1), 열(15,000 + 1) 의 크기로 생성하여 0번째가 아닌 1번째 인덱스 부터 값을 넣었기 때문에 weights에서는 0번쨰부터 값을 시작했으므로 -1을 해줘야한다.

 

<점화식>

첫번째 오류. IndexError

조건을 보면 추의 개수는 최대 30, 추의 무게는 최대 500, 구슬의 무게는 최대 40,000이라고 하였다.

추를 이용하여 만들 수 있는 구슬의 최대 무게 = 30 * 500 = 15,000 이 된다.

즉 구슬의 무게의 범위가 최대 40,000이지만 실제로는 15,000까지만 만들 수 있으므로 15,000보다 큰 값이 들어오면 IndexError 가 난다.

 

2) 소스코드

import sys
input = sys.stdin.readline

# 사용한 추의 개수, num개의 추를 사용하여 만든 구슬의 무게
def cal(num, weight):
  # 사용할 수 있는 추의 개수를 넘어가면 종료
  if num > n:  return

  # 1. num번째까지 추로 weight 무게를 만들 수 있음이 이미 기록되어있으면 종료
  if d[num][weight]:  return
  # 2. num번째까지 추로 weight 무게를 만들 수 있음을 체크
  d[num][weight] = True 
    
  # 3가지 경우 수행
  cal(num + 1, weight + weights[num - 1])  # 추의 무게를 더함
  cal(num + 1, abs(weight - weights[num - 1]))  # 추의 무게를 뺌
  cal(num + 1, weight)  # 추를 사용하지 않음

n = int(input())  # 추 개수
weights = list(map(int, input().split()))  # n개의 추의 무게
m = int(input())  # 구슬 개수
target = list(map(int, input().split()))  # m개의 구슬 무게
# d[i][j]: i번째까지 추를 사용했을 때 j무게를 만들 수 있는지 여부
d = [[False] * 15001 for _ in range(31)]

cal(0, 0)  # 지금까지 사용한 추 개수, 추로 만든 구슬의 무게를 0으로 시작

# m개의 구슬 무게를 확인할 수 있는지
for t in target:
  # 만들 수 있는 구슬의 무게는 30*500이 최대임
  if t > 15000:  print("N", end=" ") 
  elif d[n][t]: print("Y", end=" ")
  else:  print("N", end=" ")

 

[참고] https://my-coding-notes.tistory.com/157

[🥇2 / 백준 2629 / 파이썬] 양팔저울