양팔저울 [백준 2629] - python

import sys
input = sys.stdin.readline

def BOJ2629() :
  n = int(input())
  weight = list(map(int, input().split()))
  input()
  need_check = list(map(int, input().split()))

  dp = [[0 for _ in range(40001)] for _ in range(n)] 
  dp[0][weight[0]] = 1

  for i in range(1, n) :
    dp[i][weight[i]] = 1 

    for j in range(40001) :
      if dp[i-1][j] == 1 :
        dp[i][j] = 1
        dp[i][j + weight[i]] = 1
        dp[i][abs(j - weight[i])] = 1

  for i in need_check :
    if dp[n-1][i] :
      print("Y", end = " ")
    else :
      print("N", end = " ")

BOJ2629()

 

접근방법 :

1. dp는 추의 개수와 무게로 이루어진 배열이다.

ex) dp[0][10] 은 1개로 10의 무게를 잴수 있을까에 대한 값
dp[1][10] 은 2개로 10의 무게를 잴수 있을까에 대한 값
dp[2][10] 은 3개로 10의 무게를 잴수 있을까에 대한 값

 

2. dp를 탐색하면서 하나 이전의 개수로 구했던 값에서 더하고 뺀 값들은 잴수 있음을 표현해주었다.

 

    ex) 무게가 3인 추 하나를 이용해서 3을 재었다면 

    무게가 2인 추 하나가 추가되면 잴수 있는 무게들은

    1(3-1), 2, 3, 5(3+2) 총 4개가 된다.  

 

 

https://www.acmicpc.net/problem/2629

2629번: 양팔저울