바둑이 승차
생성일: 2022년 2월 3일 오후 6:15
구현 코드
# 바둑이 승차 (DFS)
import sys
sys.stdin = open("input.txt", "rt")
def DFS(index, sum):
global res
if index == n:
if sum < c and sum > res:
res = sum
else:
return
else:
DFS(index+1, sum+l[index])
DFS(index+1, sum)
if __name__ == "__main__":
c, n = map(int, input().split())
l = []
for _ in range(n):
l.append(int(input()))
res = 0
DFS(0, 0)
print(res)
- 문제점 : n이 높아지면 실행 시간이 너무 길어져서 오답 처리가 된다.
모범답안
# 바둑이 승차 (DFS)
import sys
#sys.stdin = open("in5.txt", "rt")
def DFS(index, sum, tsum):
global res
if sum + (total-tsum) < res:
return
if sum > c:
return
if index == n:
if sum > res:
res = sum
else:
return
else:
DFS(index+1, sum+l[index], tsum+l[index])
DFS(index+1, sum, tsum+l[index])
if __name__ == "__main__":
c, n = map(int, input().split())
l = []
for _ in range(n):
l.append(int(input()))
res = 0
total = sum(l)
DFS(0, 0, 0)
print(res)
차이점
- Cut Edge Tech (가지치기)
-
내가 구현한 코드에서의 문제점인 실행시간을 대폭 줄일 수 있도록 조건문을 걸어서 정답의 조건에서 벗어난 경우 곧바로 함수를 return하도록 구성되어었다.
if sum + (total-tsum) < res: return
-
위의 코드가 추가 하여 트리 구조를 재귀를 통해 계속해서 검사를 하는 도중에 전체 리스트의 합(total)에서 현재까지 검사한 수들의 총합(tsum)을 뺀 값과 sum을 더했을 때(즉, 앞으로 트리에 속한 남은 값들을 전부 더한다고 가정했을 때) res 보다 작다면 끝까지 계산을 해서 더해도 정답(res)를 갱신할 수 없는 경우에 해당 되기 때문에 return으로 빠져 나오는 구조이다.
-
Author And Source
이 문제에 관하여(바둑이 승차), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/바둑이-승차저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)