가능한 시험 점수 Python (SW Expert Academy)

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

SW Expert Academy

 

1. 문제 설명

 

영준이는 학생들의 시험을 위해 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. 코드

처음에 문제를 보았을 때 조합을 만들어 실행하면 되겠다고 생각하여 기존의 조합 코드를 이용하여 작성하였습니다. 결과는 올바르게 나오는 것 같았지만 제출했을 때 시간 초과가 떠서 다른 방법을 사용해야 했습니다. DP를 활용하는 느낌을 받았는데, 새로 추가할 결과값이 기존에 있는지를 확인하는 조건문에서 score_check를 만들지 않고 if n+k in result_scroe를 사용하였는데 똑같이 시간 초과가 났습니다. 아마 결과값에 있는지 확인하는 과정이 반복문을 한번 더 수행하는 것과 같아서 시간 초과가 난 것 같았습니다. 결과적으로 인덱스를 이용하여 받아온다면 시간이 더 빨리 질 것이라 생각하여 코드를 수정한 결과 pass가 되었습니다.

 

아래가 작성한 코드입니다.

T = int(input())
for t in range(1, T+1):
    N = int(input())
    arr = list(map(int, input().split()))
    # 가능한 점수를 결과에 추가했는지 확인하는 배열
    score_check = [1] + [0] * sum(arr)
    # 결과를 저장할 배열(0점은 무조건 나와서 미리 넣어둠)
    result_score = [0]
    # 각 문제의 점수를 기존 결과값에 더하며 최종 결과값을 만드는 반복문
    for k in arr:
        # 반목분을 수행하며 리스트 내용이 바뀌기 때문에 임시 리스트 생성
        temp = list(result_score)
        for n in temp:
            # 기존 결과에 없으면 추가하는 조건문
            if not score_check[n+k]:
                score_check[n+k] = 1
                result_score.append(n + k)
    print('#{} {}'.format(t, len(result_score)))