[백준] 2437 - 저울

2437-저울
무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램

Python3 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split())
arr.sort() # 리스트를 오름차순으로 정렬

target =1
for x in arr:
	if target<x: # target보다 다음 추가 더 큰 경우
		break
	target+=i # 하나씩 더하기

print(target)

어떻게 풀어야 할지 모르겠어서 답을 참고하였다..

풀이방법

1. 리스트를 오름차순으로 정렬해주고 하나씩 더하면서 해당 수를 리스트의 다음 요소(다음 추)와 비교
2. 비교해서 다음 추가 그동안 더했던 추들의 합보다 더 크다면 해당 값은 주어진 N개의 추들로 만들 수 없음.

이렇게 풀면 정답이 나오는데 왜 그런건지 아직 이해가 잘 안 간다.🥲

자세하게 풀이 과정을 적은 블로그가 있으니 참고해서 이해해보기!
https://seongonion.tistory.com/127