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

SW Expert Academy

---

🗒️파이썬 코드 풀이

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    lst = list(map(int,input().split())) # 입력값
    result = [0] # 결과값 저장
    visit = [1] + [0] * sum(lst) # 방문 체크
    

    for i in range(len(lst)) :
        for j in range(len(result)):
            if visit[lst[i]+result[j]] == 0 : # 방문은 안했을 경우
                visit[lst[i]+result[j]] = 1
                result.append(lst[i]+result[j])  # 결과값에 저장
    print(f"#{tc} {len(result)}")

1. 입력값 / 결과값 저장 / 방문 체크 리스트 (점수 총 합 크기만큼)

2. 방문 안했을때의 경우 

2- 1. result 모든 값과 점수를 더함 (result는 새로운 점수가 나올때마다 추가)

 

📌시간 타임 오버

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    lst = list(map(int,input().split()))
    ans = set() # 집합으로 중복 제거

    def dfs(n,point) : 
        if n == N :
            ans.add(point) # 집합에 point 넣어주기
            return

        dfs(n+1,point+lst[n]) # 선택됐을 때 경우
        dfs(n+1,point) # 선택되지 않았을 때 경우

    dfs(0,0)
    print(f"#{tc} {len(ans)}")

딱 문제를 보고 DFS로 문제를 풀야겠다 생각했다. ( 선택됐을 때 and 선택되지 않았을때)

심지어 초반에 dfs 함수 호출 위에 for문을 쓰기도 했었다.

 

N(1 ≤ N ≤ 100) 이기 때문에 시간초과가 나는게 당연하다. 

---

 

📚문제

 

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

[출력]

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