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

난이도 : D4

문제번호 : 3752

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

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 3 2 3 5 10 1 1 1 1 1 1 1 1 1 1	#1 7 #2 11

---

2. 문제풀이

구할수 있는 최대 수만큼의 리스트를 만들어 주고 나온 수를 체크하기 위한 변수를 만들어 준다. 초기값은 0으로 셋팅한다. 이번 풀이는 기존에 나온 수를 이용하여 값을 찾는 방식이다. 들어온 수를 순회하며 값을 더하는데 기존에 구한 값에 더하는 방식으로 정답을 구한다. 예를 들어서 2, 3, 5가 나온다고 하면 경우의 수는 (0, 2, 3, 5, 7, 8, 10) 7가지가 된다.  이걸 이용하여 처음 2가 나오면 가지고있는 값은 0하나였으니까 0에 2를 더한 값을 넣어준다. 그렇다면 나온값은 [0, 2]가 된다. 이제 3이 나온다. 나온수에 더하게 되면 [0, 2, 3, 5] 가 된다. 5가 나온다. 나온수에 더하게 되면 [0, 2, 3, 5, 7, 8, 10]이 된다. 기존의 값을 이용하여 구하게 된다면 시간을 많이 줄일 수 있다.

---

3. 소스코드

#D4 3752 가능한 시험 점수
 
 
for t in range(1, int(input())+1):
    N = int(input())
    scores = list(map(int, input().split()))
    #수가 나왔는지 체크
    check = [1] + [0] * sum(scores)
    #나온 수 체크
    visit = [0]
    for i in scores:
        temp = visit[:]
        for j in temp:
            if not check[i + j]:
                #사용한 수는 체크
                check[i + j] = 1
                #이미 계산된 수에 더 계산하기 위해 추가한다.
                visit.append(i + j)
    print('#{} {}'.format(t, len(visit)))