글 읽기 - 왜 시간초과가 나는지 모르겠습니다.

effort98 2년 전 0

전 이미 부분원소들의 합인 sum이 이미 a에 있으면 추가하지 않는 방법을 썼지만 이렇게 하면 시간오류가 나고

이 방법이 아닌 a = set(a) 를 이용하면 시간이 적게 드네요. 무슨 원리인거죠

import sys
input = sys.stdin.readline
a = []
def dfs(idx, sum):
    global cnt
    if idx >= n:
        return
    sum += s_[idx]
    if sum not in a:
        a.append(sum)
    dfs(idx + 1, sum - s_[idx])
    dfs(idx + 1, sum)
n = int(sys.stdin.readline())
s_ = list(map(int, input().split()))
cnt = 0
dfs(0, 0)
for i in range(1, 2000000):
 if i not in a:
   print(i)
   break

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 시간초과가 나는지 모르겠습니다.

effort98 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말