[BOJ 2437, Python 3] 저울

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

2437번: 저울

 

 

풀이

정석 풀이는 아니지만 무게를 측정할 수 있다 = 더하기를 적절히 이용해서 무게를 만들어야 한다.

여기서 키워드를 얻어서 추를 오름차순으로 정렬한 뒤 첫 번째 추를 리스트에 넣어주고, 두 번째 추부터는 리스트에 있는 추에 전부 현재 인덱스의 추를 모두 더해준다음 현재 추를 리스트에 넣어주고, 리스트를 오름차순으로 정렬하는 과정을 반복하였습니다.

저러고 출력을 해보면 신기하게 (1번째 추부터 i-1번째 추까지의 합) + 1 < (i번째 추의 무게)일 때만 중간에 구멍이 뚫리는 것을 확인할 수 있고, (1번째 추부터 i-1번째 추까지의 합) + 1 >= (i번째 추의 무게)이면 (1번째 추부터 i번째 추까지의 합) + 1이 답인 것을 확인할 수 있습니다.

 

증명은 https://www.acmicpc.net/board/view/45841 를 보면 수학적 귀납법으로 증명할 수 있다고 하네요

 

 

코드

n = int(input())
arr = sorted([*map(int, input().split())])
if arr[0] != 1:print(1);exit()
val = arr[0]
for i in range(1, n):
    if val + 1 < arr[i]:
        print(val + 1)
        exit()
    val += arr[i]
print(val + 1)