[백준] 2437 저울 (Python/파이썬)

<문제 링크>

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

2437번: 저울

<풀이 전략>

1. 그리디 문제로 정답코드를 보면 매우 단순한데 아이디어를 떠올리기까지가 매우 힘들다.
2. 핵심 아이디어는 다음과 같다.
   1. 현재까지 측정 가능한 무게의 최댓값을 ans라고 하면 (1 -  ans)의 값들을 측정할 수 있다.
   2. 오름차순으로 정렬된 무게추들 중에서 하나의 무게추(weight)을 선택한다.
   3. weight <= ans라면 (1 ~ ans)의 값들을 측정할 수 있으므로 weight + 1, weight + 2 .... weight + ans도 측정할 수 있으므로, 측정 가능한 최댓값은 ans + weight이 된다.
   4. weight > ans + 1라면 ans + 1의 값은 측정 불가능하므로 해당 값이 정답이 된다.
   5. 단 1, 1, 1, 1 혹은 1, 2, 3, 4 처럼 1 ~ sum(weights)까지 모두 측정이 가능한 경우는 sum(weights) + 1이 정답이 되므로 마지막에도 출력 코드를 넣어줘야 한다.

 

<정답 코드>

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 220927 2437 저울

# 정답코드

# N: 저울 추 개수, weights: 저울 추의 무게
N = int(input())
weights = list(map(int, input().split()))

# 오름차순 정렬
weights.sort()

# solve: 그리디로 문제 해결
def solve():
    # ans: 현재 측정 가능한 무게의 최댓값 + 1 (측정할 수 없는 무게의 최솟값 )
    ans = 1
    for weight in weights:
        # 현재 선택한 무게추가 현재까지 측정 가능한 무게의 최댓값보다 클 경우 (현재 무게 최댓값 + 1)은 측정할 수 없다.
        if ans < weight:
            print(ans)
            return
        # 현재 선택한 무게추(weight)가 현재까지 측정 가능한 무게의 최댓값(ans)보다 작을 경우 ans <= K <= ans + weight은 측정 가능하므로 측정 가능한 무게의 최댓값에 weight을 더해준다.
        ans += weight

    # 1 ~ sum(weights)까지 모두 측정이 가능할 경우
    print(ans)
    return


solve()