[SWEA] D4 3752 가능한 시험 점수 (Python)

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE

 

문제

영준이는 학생들의 시험을 위해 N개의 문제를 만들었다.

각 문제의 배점은 문제마다 다를 수 있고, 틀리면 0점 맞으면 배점만큼의 점수를 받게 된다.

학생들이 받을 수 있는 점수로 가능한 경우의 수는 몇 가지가 있을까?

예를 들어, 첫 번쨰 Testcase의 경우, 총 문제의 개수는 3개이며 각각의 배점은 2, 3, 5점이다

가능한 시험 점수의 경우의 수를 살펴보면 0, 2, 3, 5, 7, 8, 10의 7가지가 있다.

두 번째 Testcase의 경우, 총 문제의 개수는 10개이며 각각의 배점은 모두 1점이다.

가능한 시험점수의 경우의 수를 살펴보면 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10으로 모두 11가지이다.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 자연수 N(1 ≤ N ≤ 100)이 주어진다.

두 번째 줄에는 각 문제의 배점을 의미하는 N개의 자연수가 공백으로 구분되어 주어진다. 배점은 1이상 100이하의 자연수이다.

[출력]

각 테스트 케이스마다 학생들이 받을 수 있는 점수의 경우의 수를 출력한다.

 

2  //Test Case 수 3  //Test Case 1, N = 3 2 3 5 10 1 1 1 1 1 1 1 1 1 1

#1 7 #2 11

 

풀이

문제를 보자마자 그냥 조합 구해서 시험점수 계산해서 set으로 중복제거하면 되겠다고 생각하고 재귀를 활용해 DFS로 문제를 풀었으나... 장렬히 시간초과를 맞게 되었다...

최대 테스트 케이스가 100개나 되기에 최악의 경우 2^100의 계산을 해야 했기에 시간초과가 난 것이라 생각된다.

시험점수 최대 합만큼의 방문배열을 만든뒤 점수를 뽑아 결과들과 더해나가고 그 결과값이 방문배열에 없다면 중복이 아니기에 결과에 더해준뒤 최종적으로 결과배열의 길이를 출력하면 된다.

테스트 케이스 1번을 가지고 설명하자면 대략적으로 이런 Flow로 해결이 된다.

 

시험점수 = 2 3 5

1단계(준비)

방문배열= 1 0 0 0 0 0 0 0 0 0 0

결과: 0

 

2단계 (시험점수 2점을 뽑음)

0+2 = 2 >> 2에 해당하는 방문배열이 존재하는지 비교 없으므로 방문배열 체크 및 결과에 저장

방문배열= 1 0 1 0 0 0 0 0 0 0 0

결과: 0 2

 

3단계(시험점수 3점을 뽑음)

0+3 = 3 >>방문배열에 없으므로 체크 및 결과 저장

2+3 = 5 >> 방문배열에 없으므로 체크 및 결과 저장

방문배열 = 1 0 1 1 0 1 0 0 0 0 0

결과: 0 2 3 5

 

4단계(시험점수 5점을 뽑음)

0+5 = 5 >>방문 배열에 존재하므로 pass

2+5 = 7 >>방문배열에 없으므로 체크 및 결과 저장

3+5 = 8 >> 방문배열에 없으므로 체크 및 결과 저장

5+5 = 10 >> 방문배열에 없으므로 체크 및 결과 저장

결과: [0 2 3 5 7 8 10] >> 길이 도출하면 7

 

코드

깔끔하게 시간초과된 안타까운 DFS 코드

T = int(input())
for t in range(T):
    N = int(input())
    score = list(map(int,input().split()))
    bit = [0,1]
    result = set()
    def test(idx,point): 
        if idx == N:
            result.add(point)
            return
        for i in range(2):
            point += score[idx] * bit[i]
            test(idx+1,point)
    test(0,0)
    print('#{} {}'.format(t+1,len(result)))

 

위의방법대로 Pass한 코드

T = int(input())
for t in range(T):
    N = int(input())
    score = list(map(int,input().split()))
    score_visit = [1] + [0] * sum(score) # 0 점은 반드시 존재
    score2 = [0] 
    for point in score: # 점수를 뽑아서 
        for i in range(len(score2)): # 결과와 더해 나간다.
            if not score_visit[point+score2[i]]: # 더한 값이 방문한적 없으면 중복이 아니기에 
                score_visit[point+score2[i]] = 1 # 방문 배열에 체크하고
                score2.append(point+score2[i]) # 결과에 더해준다
    print('#{} {}'.format(t+1,len(score2)))