[SWEA] 3752. 가능한 시험 점수★

3752. 가능한 시험 점수

틀린 문제 풀이1

• 런타임 에러 발생
• combinations 사용

from itertools import combinations
t = int(input())

for i in range(1, t + 1):
    # n : 총 문제 수
    n = int(input())
    score = list(map(int, input().split()))
    num = set()

    for k in range(1, n):
        scorelist = list(combinations(score, k))
        for s in scorelist:
            ans = 0
            for t in s:
                ans += t

                if ans not in num:
                    num.add(ans)

    print(f"#{i} {len(num) + 2}") 

틀린 문제 풀이2

• 제한 시간 초과
• DFS를 활용한 조합 사용

import sys
sys.stdin = open("input.txt", "r")

t = int(input())

for a in range(1, t + 1):
    # n : 총 문제 수
    n = int(input())
    score = list(map(int, input().split()))
    num = set()


    def dfs(idx, r, start):
        if idx == r:
            num.add(sum(result))
            return

        for i in range(start, len(arr)):
            result[idx] = score[arr[i]]
            dfs(idx + 1, r, i + 1)


    arr = [i for i in range(n)]
    for i in range(1, n + 1):
        result = [0] * (i)
        dfs(0, i, 0)

    print(f"#{a} {len(num) + 1}")

정답 문제 풀이

• DP 사용

import sys
sys.stdin = open("input.txt", "r")

t = int(input())

for a in range(1, t + 1):
    # n : 총 문제 수
    n = int(input())
    scorelist = list(map(int, input().split()))
    
    # 결과 저장할 리스트: result
    result = [0] * (sum(scorelist) + 1)
    result[0] = 1

    for score in scorelist:
        # 뒤에서 앞으로
        for i in range(len(result) - score, -1, -1):
            # result[가능한 점수]가 있다면
            if result[i]:
                # result[그 점수 + 방금 얻은 점수]에 1을 넣어준다.
                result[i + score] = 1

    print(f"#{a} {sum(result)}")

---

참고 자료

• DFS 순열/조합
• 참고 코드