SWEA 3752 가능한 시험점수(python)

dfs로 풀려고 했지만 테스트 케이스가 100개일 경우 2^100번을 해야하기 때문에 시간 초과로 실패🥲

📖 실패 답안

def dfs(result, cnt):
    if cnt == N:
        answer.add(result)
        return
    dfs(result + score[cnt], cnt + 1)
    dfs(result, cnt + 1)

T = int(input())

for _ in range(T):
    N = int(input())
    score = list(map(int, input().split()))

    answer = set()
    dfs(0, 0)

    print(f'#{_+1} {len(answer)}')

dp로 풀어야겠다고 생각했다.

1 . 각 점수를 순회할 때마다, possible_scores에 있는 기존의 점수들에 현재 점수를 더한 새로운 점수들을 임시 집합 tmp에 추가
2. tmp에 있는 새로운 점수들을 possible_scores에 업데이트하여 가능한 점수의 조합을 추가

📖 답안

tc=int(input())

for _ in range(tc):
    n=int(input())
    scores=list(map(int,input().split()))

    possible_scores={0}

    for score in scores:
        tmp=set()
        for ps in possible_scores:
            tmp.add(score+ps)
        possible_scores.update(tmp)
        print(possible_scores)
    print(f'#{_+1} {len(possible_scores)}')