SWEA 3752 가능한 시험점수

D4

문제

영준이는 학생들의 시험을 위해 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이하의 자연수이다.

[출력]

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

풀이과정

맨처음 풀이는 시간초과가 났다...

T = int(input())


for tc in range(1, T+1):
    N = int(input())
    score = list(map(int, input().split()))
    cnt = 0

    case = set()
    for i in range(1<<N):
        sub_case = []
        for j in range(N):
            if i & (1<<j):
                sub_case.append(score[j])
        case.add(sum(sub_case))

    result = len(case)

    print("#{} {}".format(tc, result))

풀이

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    # 배당 점수 초기화
    scores = list(map(int, input().split()))
    # 방문검사를 위한 리스트를 만든다.
    # 총합의 개수만큼 만들어 준다.
    visited = [0] * (sum(scores)+1)
    # 0점은 무조건 존재 하므로 만들어준다.
    visited[0] = 1

    # 점수들을 돌면서 확인한다.
    for score in scores:
        # 해당 숫자를 제외한 수부터 차례로 내려오면서 검사해본다.
        # 왜냐하면 가장 해당 원소를 더했을 때 가장 큰 수가 나와야 하기 때문이다.
        for i in range(len(visited) - score, -1, -1):
            # 만일 해당 원소를 검사하기 전에 이미 합이 있다면
            # 그곳에서 한번 더 더해준다.
            if visited[i]:
                visited[i + score] = 1

    # visited에 찍힌 곳이 합으로 나올 수 있는 곳이다.
    print("#{} {}".format(tc, sum(visited)))