백준 2629번 파이썬으로 풀기

문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 1> 구슬이 3g인지 확인하는 방법 (1은 1g인 추, 4는 4g인 추, ●은 무게를 확인할 구슬)

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

 

<그림 2> 구슬이 5g인지 확인하는 방법

입력

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

 

출력

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

 

 

생각

첫번째 줄에는 추의 개수(30개 이하)두번째 줄에는 추의 무게들이 가벼운 순서대로(500g 이하)세번째 줄에는 구슬의 개수(7개 이하)네번째 줄에는 구슬의 무게(40000이하)

 

출력은 Y와 N으로 차례대로 출력

 

주어진 추를 모두 거쳐 무게를 만드는 방법은 3가지가 존재한다.1. 추의 무게를 더한다.2. 추의 무게를 뺀다.3. 추를 사용하지 않는다. 2차원 배열 dp에는 다음과 같은 정보가 저장된다.dp[weight][n] -> n번 추까지 사용했을 때 무게 weight를 만들 수 있는지에 대한 정보

코드+설명

# 입력 받기
n, k = int(input()), list(map(int, input().split()))  # 추의 개수와 추의 무게 리스트 입력 받기
m, l = int(input()), list(map(int, input().split()))  # 무게를 확인할 리스트 입력 받기

# dp 배열 초기화
# 추의 무게는 최대 500이므로 [[추의 개수*500]*추의 개수]로 배열을 구성한다.
dp = [[0 for j in range((i + 1) * 500 + 1)] for i in range(n + 1)]

# 결과 리스트 초기화
r = []

# 재귀 함수를 통해 가능한 모든 무게를 만들 수 있는 경우를 계산하는 함수 정의
def cal(num, weight):
    if num > n:
        return
    
    if dp[num][weight]:
        return
    
    dp[num][weight] = 1
    
    cal(num + 1, weight)                # 해당 추를 사용하지 않는 경우
    cal(num + 1, weight + k[num - 1])   # 해당 추를 사용하는 경우
    cal(num + 1, abs(weight - k[num - 1]))  # 해당 추를 사용하지만 무게를 뺀 경우

# 초기 호출
cal(0, 0)

# 결과 확인
for i in l:
    if i > 30 * 500:  # 30개의 추를 사용했을 때 무게가 최대 30*500을 넘어가면 무조건 'N'
        r.append("N")
        continue
    if dp[n][i] == 1:
    	r.append("Y")
    else:
    	r.append("N")
print(*r)

 

 

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

2629번: 양팔저울

 

느낀점

이번 문제는 정말 하나도 모르겠어서 검색만으로 문제를 풀었다. 좀 더 공부하고 dp에 대해서도 공부한 다음 다시 문제를 풀것이다.