[baekjoon] 백준 2437번(파이썬): 저울

문제

2437번: 저울

- 하나의 양팔 저울을 이용하여 물건의 무게를 측정한다.

- 무게가 양의 정수인 N개의 저울추가 있다.

- 저울추를 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 문제이다.

- 예를 들어, 무게각 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

- N은 1 이상 1,000 이하이다.

- 각 추의 무게는 1 이상 1,000,000 이하이다.

알고리즘

- 저울추의 개수를 입력받는다.

- 저울추의 무게를 입력받아 리스트 형식으로 변수에 넣는다.

- 저울추의 무게를 비교하기 위해 오름차순으로 정렬한다.

- 저울추의 무게와 비교할 변수를 만들어 양의 정수의 최솟값인 1로 초기화시킨다.

- 변수는 반복문을 통해 저울추의 무게를 더해준다.

- 변수와 저울추의 무게를 비교하고 저울추의 무게가 더 크다면 변수의 값은 저울추로 만들 수 없는 양의 정수의 최솟값이 된다. 

코드

import sys

n = int(sys.stdin.readline())
w = list(map(int, sys.stdin.readline().split()))
# 추의 무게 오름차순 정렬
w.sort()
# target의 초기값(양의 정수의 최솟값은 1이기 때문)
target = 1
# 추의 무게를 더한 target과 다음 추의 무게를 비교
for i in w:
    # 추의 무게가 더 크면 그때의 target을 측정할 수 없다.
    if target < i:
        break
    # target의 추의 무게를 더해준다.
    target += i

print(target)

결과

위 코드에서 반복문 맨 위에 print(target, i)를 작성하게 되면 target과 저울추의 무게를 비교하는 과정을 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 처음에 target(양의 정수의 최솟값인 1)과 저울추의 무게 1을 비교한다. 이때 target과 저울추의 무게가 같으므로 저울추의 무게로 target을 측정할 수 있게 된다. 그리고 target은 비교한 저울추와 자신을 더한 값을 받게 된다. 다음으로 target의 값 2와 저울추의 무게 1을 비교하면 target의 값이 더 큰 것을 확인할 수 있게 된다. target의 값이 더 크게 되면 그전에 있던 저울추의 무게로 측정할 수 있다는 것이 된다. 왜냐하면 target의 무게는 그전에 있던 저울추의 합이기 때문이다. 다음으로 7번째 상황을 보도록 하자. 7번째 상황에서는 target의 값은 21이고 저울추의 무게가 30인 것을 확인할 수 있고 그렇기 때문에 그전에 있는 저울추를 가지고 21을 측정할 수 없다는 것을 확인할 수 있다.

따라서 코드를 분석하게 되면 저울추의 무게는 오름차순으로 정렬했고 정렬한 무게를 순서대로 target과 비교하는 것을 알 수 있다. 이때 양의 정수의 최솟값인 1을 더한 target의 무게보다 큰 저울추가 있다면 target의 무게보다 큰 저울추를 제외하고 그보다 작은 저울추를 가지고 target의 무게를 측정해야 한다. 그러나 그보다 작은 저울추를 모두 더하고 양의 정수의 최솟값인 1을 더한 값이 target이기 때문에 그전에 있는 저울추로는 target을 측정할 수 없다는 것을 확인할 수 있다.

github

junjange/CodingTest