[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 만들 수 없는 금액

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 만들 수 없는 금액

• 내 풀이

  import sys
  from itertools import combinations
  input = sys.stdin.readline
  
  n = input()
  coins = list(map(int, input().split()))
  coins.sort()
  result = 0
  arr = [0] * (sum(coins)+1)
  
  for i in range(1, len(coins)+1):
      for combi in combinations(coins, i):
          arr[sum(combi)] += 1
  
  for i in range(1, len(arr)):
      if arr[i] == 0:
          result = i
          break
  
  print(result)

  내가 작성한 코드는 아마 시간초과가 뜰 것 같다. 역시나 조합(combination)을 사용하는 것은 큰 부담이다.

• 책 풀이

  n = int(input())
  data = list(map(int, input().split()))
  data.sort()
  
  target = 1
  for x in data:
      if target < x:
          break
      target += x
  
  print(target)

  뭔가 굉장히 신기했던 풀이. 직접 손으로 했을 때도 신기했다. 다시 풀어봐야겠다.