2437: 저울

문제 링크

2437: 저울

구현 방식

• 수직전을 사용하는 아이디어를 참고했다

• 구간 [1, 10]에서 무게 5인 추가 추가된다면 -> [1+5, 10+5]을 추가로 측정할 수 있음 -> 총 구간은 [1, 15]가 됨

• 구간 [1, 5]에서 무게 7인 추가 추가된다면 -> [1+7, 10+7]을 추가로 측정할 수 있음 -> 여기선 구간 [6, 7]은 측정이 불가함

• 위의 두 예시를 통해 알 수 있듯이, 기존 구간이 [0, A]이고 추가로 측정할 수 있는 구간이 [W[i], B]일 때, W[i] <= A+1을 만족해야 두 구간이 끊어지지 않음
  -> 따라서 W를 오름차순 sort하고 위의 방식으로 진행했을 때, 처음으로 끊어지는 구간의 첫번째 값이 측정할 수 없는 최솟값이 됨

코드

import sys

N = int(sys.stdin.readline().strip()); W = list(map(int, sys.stdin.readline().strip().split())); W.sort()

answer = 1
for weight in W:
    if answer < weight: break
    answer += weight
print(answer)