[파이썬/python] SWEA - 3752 가능한 시험 점수

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

---

문제 설명

1. N개의 문제가 주어진다.
2. 각 문제마다 배점이 다르며, 틀리면 0점 맞으면 배점만큼의 점수를 받을 수 있다.
3. 학생들이 받을 수 있는 점수의 경우의 수를 모두 구한다.

 

---

풀이

단순 true, false인 것을 보고 먼저 떠오른 것은 비트마스킹이었다.

 

하지만 문제의 조건에서 $N = 100$이기 때문에 $2^{100} = 10^{30}$만큼의 연산이 필요하게 되어 시간 초과가 발생하게 된다.

 

따라서 경우의 수를 압축할 수 있는 방법을 떠올렸고, Set을 사용해서 문제를 풀었다.

 

Set배열에 가능한 점수를 매번 넣어가며 완전탐색을 진행하면 중복값을 제외하고 검사가 가능하다.

 

N개의 원소를 순회하면서 set 배열에 들어있는 점수에 현재 원소의 값을 더해나간다.

 

이 경우 최악의 연산 횟수는 100*{현재까지의 점수 조합 개수}이다.

나올 수 있는 점수 조합의 개수는 $N^2$이므로 10000개이다.

 

즉 $100*10000 = 10^6$의 연산으로 문제 풀이가 가능했다.

 

문제가 너무 쉽게 풀려서, 이렇게 푸는 게 맞나 싶어서 다른 방식을 생각해 봤는데, 인덱스마다 방문 처리를 하는 방식으로도 풀릴 수 있을 것 같았다.

 

배점은 최대 1~100이므로 나올 수 있는 최대 점수인 10000까지 배열을 생성한 후

각 인덱스마다 N개의 원소를 정말탐색하며 num [i][j] = 1로 바꿔준다.

 

모든 탐색을 마치고 num배열을 정말탐색하여 경우의 수를 더한다.

 

이럴 경우에는 순수 $10^6$의 연산이 나오게 되는데 set방식은 그보다 더 적게 나오니까 내가 풀이한 방식이 시간복잡도 면에서 더 유리한 것 같긴 하다.

---

코드

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

    res = set([0])

    for i in arr:
        for j in list(res):
            res.add(i + j)
    print(f'#{tc} {len(res)}')

---

시간복잡도

• 최악의 경우 $N = 10^2$, 조합의 개수 = $10^4$ 이므로 약 $O(10^6)$의 시간복잡도를 가진다.