2437번: 저울

[amm0124]

문제

백준 2437번을 풀었습니다.
백준 2437 : https://www.acmicpc.net/problem/2437

설명

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 문제입니다.

접근법

만약 어떻게 추를 잘 사용해서, 1~100까지 무게를 만들었다고 가정해봅시다. 이 말의 뜻은 1,2,3,....97,98,99,100의 무게를 성공적으로 만들었다는 것입니다. 다음 차례로는 무조건 101을 만들어야 합니다.

즉, 다시 말해서 n개의 추를 잘 사용해서 k까지 무게를 연속적으로 만들었으면, 다음은 무조건 k+1의 무게를 만들어야 한다는 것입니다. 만약 만들지 못한다면 k+1이 정답이 됩니다.

이러한 관점에서 봤을 때, 추를 정렬한 후, 내가 지금까지 연속적으로 만든 추의 무게의 최댓값을 prev라고 했을 때, 현재 사용할 추의 무게 - prev가 2보다 크거나 같으면, 더 이상 연속적인 수를 만들지 못한다는 것입니다.

예시를 들어보자면 1~5까지 무게를 다 만들 수 있는데 (prev=5), 다음 내가 사용할 추의 무게가 7이 되어버린다면 6의 무게를 만들지 못하기 때문에 정답은 prev+1이 됩니다.

소스 코드

import sys
n=int(input())
weights=list(map(int,sys.stdin.readline().split()))
weights.sort()

if weights[0]!=1 :
    print(1)
else : #일단 1은 만들 수 있음.
    prev=1 #1~prev까지는 무조건 만들 수 있음.
    for i in range(1,n) :
        if weights[i]-prev<=1 :
            prev+=weights[i]
        else :
            print(prev+1)
            sys.exit()
    print(sum(weights)+1)

마무리하며

나머지 분들 문제는 일어나서.. 잠이 너무 오네요