[python] 백준 14225 부분수열의 합

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

14225번: 부분수열의 합

 

문제 해결

• 중간에 빠진 수를 어떻게 구할 것인가?: 우선은 sort()를 통해 작은수부터 놓는 것이 우선일 것이다.
• 맨 앞의 수는 1일 것이다.
• 두 번째 수는 2가 와도 되고 1이 추가로 와도 된다.
• 두 번째 수가 1이면 세 번째는 3이하의 수가 올 것이다. (1, 2, 3 모두 가능하다는 것이다.)
• 두 번째 수가 2이면 세 번째 수는 4이하의 수가 올 것이다.(2, 3, 4 가능하다는 것이다.)
• 첫 번째 수부터 i-1번째 수까지 모두 더한 것 +1 이하의 수가 i번째 수에 오면 계속 이어서 만들 수 있다는 것을 귀납적으로 추론이 가능하다.
• 즉 i-1번째 수까지 합+1 보다 i번째 숫자가 크면 거기서 멈추고 i-1번째 수까지 합 +1은 리스트 안에서 만들 수 없다는 것을 알 수 있다.

CODE

import sys
n = int(input())
S = list(map(int, input().split()))
S.sort()
target = 0
for i in S:
    if target +1 < i : break #겹치지 않을 때에는 최소 있어야 하는 것이 1,2,4,8 ...이다. (물론 더 있어도 된다.) 이것보다 간격이 벌어지면 숫자가 없어진다는 뜻이다. 또한 i이전의 S원소를 모두 더한 것이 i 보다 작으면 i이전수 S원소를 모두 다 더한 것의+1읜 원소는 있을 수가 없다.
    target +=i
print(target+1)