[Python, 파이썬] SWEA 3752. 가능한 시험 점수

 

학생들이 받을 수 있는 점수로 가능한 경우의 수는 몇 가지가 있는지 구하는 문제.

 

 

 

T = int(input()) # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    N = int(input()) # 자연수의 개수 N
    test = list(map(int, input().split())) # N개의 시험점수
    comb = set({0}) # 점수 조합을 저장하는 list

    for i in range(N):
        for element in comb.copy(): # set은 반복 중 바꾸면 Error, 그래서 copy 해준 값으로 반복
            comb.add(element+test[i]) # 현재 탐색중인 값을 저장된 조합 리스트에 ++

    print("#%d %d" %(test_case, len(comb)))

 

 

 

[문제풀이]

---

 

 

모든 경로를 확인하는 완전 탐색 문제.

그러나 DFS+백트래킹을 사용할 시 시간 초과가 난다.

 

DFS의 시간복잡도는 2^n으로 N이 최대 100인 이 문제의 시간복잡도는 2^100으로 절대 Python에 주어진 4초 안에는 풀 수 없다. 그래서 생각해야 하는 다른 방법이 바로 DP!

 

 

중복을 방지하는 set와 시험점수 배점 배열을 각각 만든다.

우선, 처음 저장된 점수 조합은 {0} 하나뿐이다.

그리고 각 배점을 추가할 때마다 기존의 가능한 점수에 배점을 더하여 새로운 점수 조합을 만드는 과정을 반복하면 된다.

 

배점이 2만 있을 때는 set에 들어있는 값들에 2를 더하여 {0, 2}.

그리고 배점 3이 추가될 경우, {0, 2}에 각각 3을 더해 {0, 2, 3, 5}.

이 과정에서 중복은 set이 알아서 삭제하며, 이렇게 모든 배점을 반복하면 가능한 모든 점수 조합을 얻을 수 있다!