[백준] 2629번 : 양팔저울 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 여러 개의 추를 가지고 구슬의 무게를 확인하는 문제이다.

각 구슬별로 무게를 확인할 수 있는지 없는지 출력하는 문제이다.

해당 문제 총 3가지의 동작을 반복적으로 수행하며 확인하려는 구슬의 무게를 만들 수 있는지 없는지 확인하고 결과를 출력하면 된다. 따라서 재귀적으로 수행되어야 하고 만들 수 있는 무게를 저장하며 문제를 해결해야 한다.

문제에서 이뤄지는 행동 3가지를 살펴보면 아래와 같이 나타낼 수 있다.

1. 추를 저울에 놓는다.
2. 추를 저울의 반대쪽에 놓는다. (저울에서 뺀다.)
3. 추를 놓지 않는다.

3가지 행동을 하며 추를 활용해 확인할 수 있는 구슬의 무게를 찾는다.

이때 만약 추의 개수가 전체 추의 개수를 넘어가면 더 이상 진행할 수 없으므로 멈춘다.

만약 사용한 추의 무게가 이미 찾은 무게이면 확인해볼 필요가 없으므로 넘어간다.

총 사용 가능한 추의 개수가 30개이고, 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같으므로 행에 사용한 추의 개수를, 열에 양쪽 저울의 추 무게의 차이를 저장하는 2차원 배열 dp를 만들어 dp[사용한 추의 개수][양쪽 저울의 추 무게의 차이]에 구슬의 무게를 측정가능한지 여부를 저장한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 전체 추의 개수를 입력받는다. weight_count = int(sys.stdin.readline())
3. 각 추의 무게를 입력받아 리스트로 저장한다. weight_list = list(map(int, sys.stdin.readline().split()))
4. 확인할 구슬의 개수를 입력받는다. bead_count = int(sys.stdin.readline())
5. 각 구슬의 무게를 입력받아 리스트로 저장한다. bead_list = list(map(int, sys.stdin.readline().split()))
6. 가지고 있는 추를 활용하여 확인할 수 있는 무게를 구하는 함수를 생성한다. def cal(num, weight)
   1. 만약 사용한 추의 개수가 전체 추의 개수보다 많아지면 더 이상 추가할 추가 없으므로 가능한 무게 확인을 멈춘다. if (num > weight_count): return
   2. 만약 사용한 추의 개수에 따른 만들 수 있는 무게가 이미 확인할 수 있는 무게라고 판별이 되어있다면 또 확인할 필요는 없으므로 확인을 멈춘다. if (dp[num][weight]): return
   3. 사용한 추의 개수에 따른 만들 수 있는 무게가 처음 확인되었다면 해당 무게를 가능한 것으로 저장한다. dp[num][weight] = True
   4. 이후 추를 저울에 놓은 결과를 확인한다. cal(num + 1, weight + weight_list[num - 1])
   5. 추를 저울의 반대쪽에 놓은(추를 저울에서 뺀) 결과를 확인한다. cal(num + 1, weight - weight_list[num - 1])
   6. 추의 개수는 늘리지만 추를 놓지 않은 결과를 확인한다. cal(num + 1, weight)
7. 전체 구슬의 개수인 30개와 구슬의 최대 무게인 40,000까지 결과를 저장할 수 있도록 2차원 배열을 생성하고 모두 False로 초기화한다. dp = [[False] * 40001 for _ in range(31)]
8. 추를 사용하지 않고 양쪽 저울을 무게의 차이가 0일 때부터 시작한다. cal(0, 0)
9. 최종적으로 가능한 모든 무게의 차를 구했다면 확인해야 하는 구슬을 하나씩 가져와 for bead_weight in bead_list
   1. 만약 모든 추를 사용한 결과에서 해당 구슬의 무게를 찾을 수 있다면 Y를 출력한다. if (dp[weight_count][bead_weight]): print('Y', end=' ')
   2. 반면에 해당 구슬의 무게를 찾을 수 없다면 N를 출력한다. else: print('N', end=' ')

728x90

3. 소스코드

import sys

weight_count = int(sys.stdin.readline())
weight_list = list(map(int, sys.stdin.readline().split()))
bead_count = int(sys.stdin.readline())
bead_list = list(map(int, sys.stdin.readline().split()))

def cal(num, weight):
    if (num > weight_count):
        return
    if (dp[num][weight]):
        return
    
    dp[num][weight] = True
    
    cal(num + 1, weight + weight_list[num - 1])
    cal(num + 1, weight - weight_list[num - 1])
    cal(num + 1, weight)
    
dp = [[False] * 40001 for _ in range(31)]

cal(0, 0)

for bead_weight in bead_list:
    if (dp[weight_count][bead_weight]):
        print('Y', end=' ')
    else:
        print('N', end=' ')