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

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn 

SW Expert Academy

 

문제를 보자마자 아 이거 조합으로 해서 set으로 중복제거한 다음 길이 출력하면 되겠다 생각하고 조합으로 풀었더니 시간초과 나서 틀렸었다.

그냥 100C50만 생각해봐도 엄청 큰 숫자인데 귀찮다고 생각안하고 풀어버렸다.

 

 

풀이는 앞에서 나온 합을 기록하여 현재 숫자와 더해 가는 방식으로 했다.

 

1번 테스트케이스를 예로 들어 설명하겠다.

방문 배열에 해당 숫자가 나온다면 표시한다. 0의 경우 반드시 나오므로 1로 세팅하고 시작한다.

 

점수는 2,3,5가 들어오고 배열 크기는 가능한 점수 중 가장 큰 값까지 하면 된다.

1 0 0 0 0 0 0 0 0 0 0      - > 초기배열

---

2 입력으로 들어온다.

배열의 가장 오른쪽 부터 1인 경우를 찾는다.

 

배열[0]이 1 이므로  0+2의 값을 1로 바꾼다.

1 0 1 0 0 0 0 0 0 0 0

---

3 입력으로 들어온다.

배열의 가장 오른쪽 부터 1인 경우를 찾는다.

 

배열[2]가 1이므로 2+3의 값을 1로 바꾼다.

1 0 1 0 0 1 0 0 0 0 0

 

배열[0]이 1이므로 0+3의 값을 1로 바꾼다.

1 0 1 1 0 1 0 0 0 0 0

---

5 입력으로 들어온다.

배열의 가장 오른쪽 부터 1인 경우를 찾는다.

 

배열[5]가 1이므로 5+5의 값을 1로 바꾼다.

1 0 1 1 0 1 0 0 0 0 1

 

배열[3]이 1이므로 3+5의 값을 1로 바꾼다

1 0 1 1 0 1 0 0 1 0 1

 

배열[2]가 1이므로 2+5의 값을 1로 바꾼다

1 0 1 1 0 1 0 1 1 0 1

 

배열[0]이 1이므로 0+5의 값을 1로 바꾼다.

1 0 1 1 0 1 0 1 1 0 1

---

마지막으로 1인 것을 세면 정답이다.

 

배열의 가장 오른쪽부터 확인하는 것은 현재 단계에서 생성된 숫자는 확인하면 안되기 때문이다.

 

tc = int(input())

visited = [0]*10001
visited_num = 0
def solv(t):
    global visited
    n = int(input())
    nums = list(map(int, input().split()))
    max_num = sum(nums)

    visited[0] = visited_num
    for num in nums:
        for idx in range(max_num,-1,-1):
            if visited[idx] == visited_num:
                visited[idx+num] = visited_num
    print('#%d %d'%(t, visited.count(visited_num)))
for t in range(1,tc+1):
    visited_num += 1
    solv(t)