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

문제 해결

1. D4 | DP

2. 얻을 수 있는 최대점수를 길이로 하는 리스트를 만든다

3. 리스트안의 값은 내가 점수를 얻을 수 있으면 1, 없으면 0으로 한다

4. 점수를 하나씩 받아서 리스트를 뒤에서부터 탐색한다

 (1) 1을 만나면(내가 이미 얻을 수 있는 점수 ex. lst[3] == 1 이면 3점은 이미 얻을 수 있는 점수이다.) 내가 꺼낸 점수를 더해서 그 지점을 1로 만들어준다.(ex. score == 2 이면 lst[5] = 1)

5. 리스트에서 1의 갯수를 세어주면 정답.

 

💨 풀이 예시] 새로 받는 점수는 2, 3, 5이다. 

얻을 수 있는 점수는 리스트는 lst = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 이렇게 구성한다. (0점은 처음부터 가능하므로 0번 인덱스의 값은 1)

먼저 2점을 꺼내보자. 뒤에서부터 하나씩 탐색하며 1이 있는지 없는지 확인한다.

lst[0] == 1 이므로, lst[0+2] = 1 을 해준다. lst = [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

 

3점을 꺼내보자. lst[2] == 1 이므로, lst[2+3] = 1 |  lst = [1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]

lst[0] == 1 이므로, lst[0+3] = 1 | lst = [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0]

 

5점을 꺼내보자. lst[5] == 1 이므로, lst[5+5] = 1 |  lst = [1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1]

lst[3] == 1 이므로, lst[3+5] = 1 | lst = [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1]

lst[2] == 1 이므로, lst[2+5] = 1 | lst = [1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1]

lst[0] == 1 이므로, lst[0+5] = 1 | lst = [1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1]

 

뒤에서부터 탐색하는 이유는 앞에서부터 하면 내가 방금 더해서 얻은 점수를 전에 있던 점수로 인식해서 계속 나아가기 때문

 

 

소스 코드

for tc in range(1, 1 + int(input())):
    n = int(input())
    scores = list(map(int, input().split()))

    # 내가 가능한 최대 점수까지 리스트를 만들어준다
    # 인덱스가 내가 얻을 수 있는 점수
    # 1이면 이미 얻을 수 있고, 0이면 얻지 못한다
    my_scores = [0] * (sum(scores) + 1)
    my_scores[0] = 1  # 0점은 가능하니까 바로 1

    # 점수를 하나하나씩 꺼내서
    for score in scores:
        # 만들어둔 리스트의 뒤에서부터 앞으로 하나씩 본다
        for i in range(len(my_scores) - score, -1, -1):
            # 이미 내가 가능한 점수가 내점수 리스트에 있으면
            if my_scores[i]:
                # 그 점수에 방금 얻은 점수를 더해서 그 점수에 해당하는 인덱스를 1로 만든다.
                my_scores[i + score] = 1

    print('#{} {}'.format(tc, sum(my_scores)))

 

출처: SW Expert Academy

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

SW Expert Academy

영준이는 학생들의 시험을 위해 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이하의 자연수이다. [출력] 각 테스트 케이스마다 학생들이 받을 수 있는 점수의 경우의 수를 출력한다.