https://www.acmicpc.net/problem/2437
시간 1초, 메모리 128MB
input :
- N (1 <= N <= 1,000)
- N개의 양의 정수 (1 <= 추의 무게 <= 1,000,000)
output :
- 측정할 수 없는 양의 정수 무게 중 최솟값을 출력
그리디는 역시 생각하는게 어렵다.
일단 정렬을 이용해서 가장 작은 추의 무게부터 따진다.
target 우리가 만드려고 하는 수를 넣어놓는다.
그래서 1부터 시작을 한다.
만약 data 배열안에 수가 1보다 커버리면? 우리는 1을 만들수 없다.
target을 출력.
1이 존재해서 만들수 있다. 그러면 target + item 해서 이는 2가 되게 된다.
그 다음 수를 꺼냈을 때 아이템이 2보다 크다면? 우리는 2를 만들 수 없다.
이러한 과정으로 진행을 한다.
target은 우리가 만드려는 수들 중 가장 큰 숫자.
item은 또다른 부품으로 만드려는 수 보다 작아야만 이 부품이 될 수 있는 것이다.
import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
data.sort()
target = 1
# 그리디...
# target 의 숫자는 우리가 만드려고 하는 숫자이다.
# data에 존재하는 요소가 이 수보다 작거나 같은 상황이라면 이를 만들 수 있다.
# 그러나 이 보다 크다면 우리는 target 보다 큰 수를 만들어 버리기 때문에
# 그 사이에 공간이 존재한다.
for item in data:
if target < item:
break
target += item
print(target)
