1학기 2주차 알고리즘 과제 (2629번 : 양팔저울)

2629번: 양팔저울 (acmicpc.net)

2629번: 양팔저울

 

문제

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

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

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

 

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

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

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

 

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

입력

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

 

 

출력

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

 

 

 

📌풀이

 

두번째 문제이다.

 

 

해당문제도 그림을 그리면서 풀면 더 이해가 잘될 것이라 판단, 위와 같이 그림을 그리면서 어떤 식으로 코드를 구현할지 고민해봤다.

 

 

✔ 위와 같이 코드를 짜려면 일단, 첫째줄에 추의 개수를 input을 사용해서 (int로 강제형변환도) 입력을 받고, 두번째 줄에 가벼운 것부터 차례대로 주어지도록 추의 무게를 변수선언후 입력받는다.

 

그리고 무게를 확인하고자 하는 구슬의 개수를 변수선언 후 입력받도록 하고, 확인하고자하는 구슬의 무게를 마지막 줄에 입력받도록한다.(자연수)

 

솔직히 말하면 해당 문제의 원리는 이해해도 코드로 바로 떠오르진않는다.

이것도 골드였구나..

 

 

시간초과가 뜨는데 시간초과를 줄여도 틀렸다는 것을 안다..

요렇게도 생각해보고 저렇게도 생각해봤는데, 어려운것도 있지만 파이썬을 최근에 안쓴지 오래돼서,,도 있을 것같다.

그래서 해당문제도 도움을 받아서 공부하면서 풀이해야할 것 같다.

 

 

[백준] 2629. 양팔 저울 (python) (velog.io)

[ 참고 학습 자료 & 코드 참고 자료 ]

[백준] 2629. 양팔 저울 (python)

 

해당 문제도 동적 계획법 (Dynamic Programming)으로 푸는 문제라고 한다.

저울의 사용자는 추를 가지고 세 가지 작업 중 하나를 수행할 수 있다.

1. 추를 왼쪽에 올린다.
2. 추를 오른쪽에 올린다.
3. 추를 올리지 않는다.

세 가지 작업을 모두 수행하는 DFS를 실행하여 문제를 해결하면된다... 그렇구나 앞전 시간에 DFS와 DP에 대해서는 확인해봤다.

import sys
input = sys.stdin.readline

# 입력값 받기

num_pends = int(input()) # 추의 개수 (<= 30)
pends = list(map(int, input().split())) # 추 (오름차순, <= 500)
num_marbles = int(input()) # 구슬의 개수 (<= 7)
marbles = list(map(int, input().split())) # 구슬의 무게 (<= 40000)

# dp table 만들기

dp = [[0]*(30*500+1) for _ in range(num_pends+1)] 
# dp[i][j]  = i 번째 까지의 추를 놓았을 때, j 무게를 만들 수 있는지

result = set()

# 관련 함수 정의

def get_result(pends, n, now, left, right):
    """
    pends : 추 목록
    n : 전체 추의 개수
    now : 이제 놓을 추의 index
    left : 왼쪽 팔의 무게
    right : 오른쪽 팔의 무게
    """
    
    new = abs(left - right)
    # 처음 함수가 호출되었을 때의 무게를 잰다.

    if new not in result: # 처음 재는 무게라면
        result.add(new) # result에 추가

    if now == n : # 재귀 탈출 조건 (모든 추를 다 올려놓았을 때)
        return 0

    if dp[now][new] == 0: # now까지의 추로 아직 무게를 잰 적이 없다면
        get_result(pends, n, now+1, left + pends[now], right) # 왼쪽에 놓기
        get_result(pends, n, now+1, left, right + pends[now]) # 오른쪽에 놓기
        get_result(pends, n, now+1, left, right) # 놓지 않기
        dp[now][new] = 1 # 무게를 재었다고 표시

get_result(pends, num_pends, 0, 0, 0)
answer = []

for marble in marbles:
    if marble in result:
        answer.append("Y")
    else:
        answer.append("N")

print(*answer)

 

• dp 테이블 생성-> dp[i][j]는 i번째까지의 추를 사용하여 무게 j를 만들 수 있는지 여부를 나타낸다.
• 0부터 num_pends * 500 까지의 무게를 저장할 수 있도록 크기를 설정
• result 세트 생성-> 구슬의 무게를 담을 세트이다.
• get_result 함수-> 재귀적으로 구슬을 올릴 수 있는 모든 경우의 수를 탐색함.
• now 인덱스의 추를 왼쪽, 오른쪽, 아예 놓지 않고 세 가지 경우로 나누어서 재귀적으로 호출 , 각 호출에서는 왼쪽 팔에 pends[now]을 더하거나, 오른쪽 팔에 pends[now]을 더하거나, 추를 놓지 않는 경우로 나누어 무게를 측정
• 새롭게 측정된 무게를 result 세트에 추가
• get_result 호출-> get_result 함수를 호출하여 모든 가능한 무게 조합을 생성
• 구슬의 무게 확인-> 각 구슬의 무게를 result 세트에 있는지 확인하고, 결과를 리스트에 추가
• 해당 무게가 있으면 "Y", 없으면 "N"을 결과 리스트에 추가
• 결과 출력-> 결과 리스트를 출력

 

이렇게 코드를 해석하면서 정리해보긴 하였으나, 첫번째 문제도 그렇고 두번째 문제도 아직은 너무 낯선 방법이라 어렵게 느껴진다.

스스로 풀지 못했으니, 두고두고 학습하면서 익숙하게 만드는 것이 방법이라 생각하고, 또 모르는 것도 당연한 것이니 앞으로 더 열심히 해야겠다는 생각이 든다.

파이썬은 자주 사용을 안하게되는데 이번기회에 파이썬과 가까워지는.... 노력을 해봐야겠다.

 

과제끄읏!