[Python] SWEA 3727 가능한 시험 점수

가능한 시험 점수

문제

• 문제 수와 각 문제 배점이 주어짐
• 나올 수 있는 시험 점수의 경우의 수를 구하기

입력

• T : 테스트 케이스 수
• N : 문제의 개수
• 두번째 줄 ~ : 각문제의 배점 (1 <= 배점 <= 100)

출력

• #<테스트 케이스 번호> <경우의 수>
• 나올 수 있는 시험 점수의 경우의 수를 출력

---

첫 풀이

from itertools import combinations

def function(N, A):
    answer = {0}
    for i in range(1, N+1):
        for j in list(combinations(A, i)):
            answer.add(sum(j))
    return len(answer)

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    A = list(map(int, input().split()))
    result = function(N, A)
    print(f"#{test_case} {result}")

• 런타임에러...
• 조합으로 겹치지 않는 값 개수를 세어준 방법이다

다른 풀이

def function(N, A):
    answer = {0}
    for i in A:
        new = set()
        for j in answer:
            new.add(i + j)
        answer.update(new)
    return len(answer)

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    A = list(map(int, input().split()))
    result = function(N, A)
    print(f"#{test_case} {result}")

• set()을 활용하여 새로운 부분합 더하여 개수 세기