[Baekjoon 2437] 저울

문제

💛Ⅱ [Baekjoon 2437 - 저울]

문제 풀이 방법

이 문제는 이코테 문제집에 Greedy 기출문제에 풀이한 적이 문제였다. 전에는 조합을 이용해서 나올 수 있는 조합을 모두 구하여 풀었는데, 정답풀이가 10줄 밖에 안되는 것을 보고 놀랐던 기억이 있다. 이 간단한 풀이를 이해하는데 꽤 오랜 시간이 걸렸다.. (이런 생각을 어떻게 할 수 있을까??)

1. 무게에 대한 정보를 오름차순으로 정렬한다.
2. 만들 수 있는지 확인할 무게는 1로 시작한다.
3. 무게를 작은 순서대로 확인한다.
   1. 현재 확인하는 무게가 현재무게보다 크다면 현재무게를 만들 수 없다.
   2. 현재 확인하는 무게가 현재무게보다 작거나 같다면 현재무게를 만들 수 있으므로 현재무게에 확인한 무게만큼 더해준다.

위의 과정이 한 번에 이해간다면 다행이지만, 나는 예시를 하나하나 생각해보면서 이해했다!!

무게가 1, 2, 3, 8이 있다고 가정하자.

1. answer = 1을 만들 수 있는지 확인한다. 현재 확인하는 무게가 1(answer ≥ 1)이므로 만들 수 있다. answer = 1+1로 업데이트한다. 이는 1까지 모든 금액을 만들 수 있다는 것을 의미한다.
2. answer = 2를 만들 수 있는지 확인한다. 현재 확인하는 무게가 2(answer ≥ 2)이므로 만들 수 있다. answer = 2+2로 업데이트한다. 이는 3까지 모든 금액을 만들 수 있다는 것을 의미한다.
3. answer = 4를 만들 수 있는지 확인한다. 현재 확인하는 무게가 3(answer ≥ 4)이므로 만들 수 있다. answer = 4+3로 업데이트한다. 이는 6까지 모든 금액을 만들 수 있다는 것을 의미한다.

4. answer = 7를 만들 수 있는지 확인한다. 현재 확인하는 무게가 8(answer < 8)보다 작으므로 만들 수 없다.

    1:1
       
    # 2 추가하여 1~3까지 가능(target = 2 >= 2)
    2:2
    3:1+2 
       
    # 3 추가하여 1~6까지 가능(target = 4 >= 3)
    4:1+3
    5:2+3
    6:1+2+3 
       
    # 8을 추가하면 7,8은 만들 수 없다(target = 7 < 8)
    7:X 
    8:X
    9:1+8
    10:2+8
    11:1+2+8
    12:1+3+8
    13:2+3+8
    14:1+2+3+8
   

풀이 코드

Python

import sys
input = sys.stdin.readline

N = int(input())
weights = list(map(int, input().split()))
weights.sort()

answer = 1
for w in weights:
    if answer < w:
        break
    answer += w

print(answer)