[SWEA] 372. 가능한 시험 점수

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn

SW Expert Academy

T = int(input())

for test_case in range(1, T + 1):
    n = int(input()) 
    scores = list(map(int, input().split()))  
    
    possible = {0} 
    
    for score in scores: 
        new_scores = set()
        
        for prev_score in possible:
        	new_scores.add(prev_score + score)
            
        possible = possible | new_scores
        
    print(f"#{test_case} {len(possible)}")

 

이 문제는 DP(동적 프로그래밍)로 해결할 수 있다.

DP[k]를 "k개 문제로 만들 수 있는 점수 집합"이라고 정의하면,

DP[k+1]은 다음 두 가지 경우를 합친 것이다:

 

DP[k+1] = DP[k] ∪ {p + score[k+1] | p ∈ DP[k]}

1) (k+1)번째 문제를 틀린 경우 → DP[k] 그대로
2) (k+1)번째 문제를 맞춘 경우 → DP[k]의 각 점수에 배점을 더함

같은 점수를 여러 방법으로 만들 수 있으므로, 중복을 자동으로 제거하는 SET 자료구조를 사용했다.