[백준] 2437번 저울 ★★★

💡문제접근

• 처음엔 combinations()을 이용하는 방법을 택했는데 역시나 시간초과(TLE)가 발생했다.
• 질문게시판에 있는 그리디 알고리즘 설명을 보고 혹시나해서 하나의 테스트케이스를 만들어서 시도해봤는데 이 방법이 쉽게 떠오르는 사람들이 대단하다고 느꼈다.
• Sum ≥ weight[i]이라면 Sum보다 작은 수를 만들 수 있다.

💡테스트케이스

4
1 2 3 6

• 예를 들어, Sum이 1+2=3이 나온다면 3보다 작은 숫자인 1,2를 측정할 수 있다는 것이다.
  또한 예를 들어, Sum이 1+2+3=6이 나온다면 6보다 작은 숫자인 1,2,3,4,5를 측정할 수 있다는 것이다.

💡코드(메모리 : 31256KB, 시간 : 44ms)

import sys
input = sys.stdin.readline

N = int(input())
weight = list(map(int, input().strip().split()))
weight.sort()

total = 1
for i in weight:
    if total >= i:
        total += i
    else:
        break
print(total)

📌 시간초과 코드(조합 활용)

from itertools import combinations
import sys
input = sys.stdin.readline

N = int(input())
weight = list(map(int, input().strip().split()))

li = []
for i in range(1, len(weight)+1):
    for j in combinations(weight, i):
        temp = sum(j)
        if temp not in li:
            li.append(temp)
li.sort()

for i in range(len(li)-1):
    if li[i+1] - li[i] == 1:
        continue
    else:
        result = li[i]
        break
print(result + 1)

💡소요시간 : 31m