- 이전 문제와 원리는 같으나 시간을 초과하는 경우가 생겨 Cut Edge 방식을 생각해봐야 한다
- 부분 집합의 o, x 존재 유무를 이진 트리로 표현하고 DFS(idx, sum) 의 방식으로 함수를 생성한다
- 시간이 초과되는 경우를 고려하여 트리의 특정 level까지 summation 한 값 + 아직 보지 않은 나머지 level의 원소의 합이 max weight value 보다 작다면 굳이 다음 level의 트리를 검사해 볼 필요가 없으므로 return을 해주는 방식
- Cut Edge 방식을 사용하면 시간이 현저하게 줄어든다, 역시 알고리즘은 아주 중요해!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
import sys
# sys.stdin=open("input", "r")
def DFS(idx, sum, tsum):
global max_weight
if max_weight > sum+(total-tsum): # Cut Edge
return
if sum > limit:
return
if idx == num:
if sum > max_weight:
max_weight = sum
else:
DFS(idx+1, sum+dogs[idx], tsum+dogs[idx])
DFS(idx+1, sum, tsum+dogs[idx])
if __name__=='__main__':
limit, num = map(int, input().split())
dogs = list(int(input()) for _ in range(num))
max_weight = -217000000
total = sum(dogs)
DFS(0, 0, 0) # (list의 인덱스 넘버, sum, tsum)
print(max_weight)
|
cs |
728x90