BOJ 23057 - 도전 숫자왕 (Python)

S2, 자료구조

풀이

1. 메모리 초과

• 발생한 수를 numbers를 통해 배열을 만드는 부분에서
  m의 범위가 크기 때문에 메모리 초과가 발생한다.

from sys import stdin
from itertools import combinations
n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
m = sum(arr)

numbers = [0] * (m + 1)
numbers[m] = 1
for i in range(1, n):
    comb = list(combinations(arr, i))
    for tmp in comb:
        numbers[sum(tmp)] = 1

print(numbers[1:].count(0))

2. 해결

• numbers배열이 아닌 set()을 통해 해결

from sys import stdin
from itertools import combinations
n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
m = sum(arr)

num = set()

for i in range(1, n + 1):
    for tmp in combinations(arr, i):
        num.add(sum(tmp))

print(m - len(num))