반응형
https://www.acmicpc.net/problem/2437
2437번: 저울
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓
www.acmicpc.net
생각해내기 정말정말 어렵다.....
그리디인지도 잘 모르겠고....
n = int(input())
nums = list(map(int, input().split()))
nums.sort()
answer = nums[0]
if answer != 1:
print(1)
quit()
for i in range(1, len(nums)):
new = nums[i]
if new - answer <= 1: # the diff is less than 1
answer += new
else:
print(answer+1)
quit()
print(sum(nums)+1)크기순으로 정렬하고
이전까지의 최대 가능한 수가 x라고 할때
새로 들어온 수(new)가 x보다 작거나, x랑 같거나, x보다 딱 1이 큰 경우는 ( => 즉 new 가 x+1 이하일때)
최대 가능한 수가 x+new까지 증가한다.
ex) 기존 x= 5라면
현재 측정가능한 수가 [1,2,3,4,5]라는 건데 new =3이라면 만약 new를 추가로 올려놓을 시
[4,5,6,7,8]가 됨. 그럼 처음꺼랑 합집합 시켜주면 [1,2,3,4,5,6,7,8]이 됨
하지만 그 범위를 벗어나면
x+1을 못만들게 되서 답이 x+1이 된다.
댓글