[백준]#2437 Python🤯

백준 2437번 - 저울

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

전체코드

import sys
input = sys.stdin.readline

N= int(input())
weight= list(map(int,input().split()))
weight.sort()
num= 1
#만들 수 없는 수 찾기
for i in weight:
  if num < i:
    break
  num+= i

print(num)

다른 사람의 코드를 보고 이해했다,,,

참고한 코드 -> https://velog.io/@sch804/파이썬-백준-2437번-저울

나는 이해하는 데에 오래 걸려서 추가적인 설명을 덧붙여본다.
처음 시작하는 값(num)을 1로 놓고 weight 의 원소 값을 더해나간다.
a~g 까지의 합을 n이라고 했을 때(a~g 의 부분집합들끼리의 합이 1~n 까지 있다는 뜻), 그 다음의 h 값을 두 경우로 나눌 수 있다.

1. 1+n 보다 작거나 같은 값일 때:
   a~g 까지의 부분집합의 합이 1~n 이기 떄문에 가능한 합이 1+n 에서 n+h 까지 늘어난다. 그 다음 원소를 볼 땐 num = 1+n+h
2. 1+n 보다 클 때:
   n 과 h 의 중간에 있는 값인 1+n 은 절대 나올 수가 없으므로 1+n 이 나올 수 없는 가장 작은 값에 속한다.

느낀점

굉장히 간단해 보이지만 생각해내기가 어려웠던 것 같다. 괜히 골드3이 아닌듯.