[python] 백준 2437 저울

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

2437번: 저울

문제 해결

• 추를 작은 것 부터 놓으면서 넘어가는 수를 찾아야한다.
• 처음에는 추를 안올려 놓으면 [0,0] 측정 가능하다는 것을 알음
• 1인 추를 올려 놓으면 [0,1] 측정 가능하다는 것을 알음
• 2인 추를 올릴려 할 때 현재 max값 1에서 현재 min값 0+2 까지 1칸 차이기 때문에 연속적이라는 것을 알음
• 따라서 2를 올려 놓으면 [0,3] 측정 가능하다라는 것을 알음
• 5인 추를 올려 놓으려 할 때 현재 max값 3에서 현재 min값 0+5를 올려 놓으면 2칸 차이기 때문에 4에서 구멍이 생긴다는 것을 알음
• 따라서 (3+1=4)이란 답을 찾을 수 있다.

 

CODE

n = int(input())
A = list(map(int, input().split()))
A.sort()
target = [0,0] # 현재 범위
for i in range(len(A)):
    target_new = [target[0]+A[i],target[1]+A[i]] # A[i]로 인한 새로운 범위
    if target_new[0] >target[1] +1: # 1칸 차이 이상 나게 되면 불연속 발생!
        break
    else:
        target = [target[0], target_new[1]]
print(target[1]+1)