[김태원 알고리즘] 바둑이 승차 (DFS)

사용 언어: Python3

문제

풀이

내 풀이

def DFS(idx, partialSum):
    global mx
    if idx > N-1:
        if partialSum <= C:
            mx = max(mx, partialSum) # max값 업데이트
    else:
        DFS(idx+1, partialSum+lst[idx]) # 승차O
        DFS(idx+1, partialSum) # 승차X

C, N = map(int, input().split())
lst = [int(input()) for _ in range(N)]

mx = -1
DFS(0, 0)
print(mx)

시간 측정

위 답안을 아래 템플릿의 ... 자리에 넣고 “복잡한 입력”에 대한 실행 시간을 측정해보자.

import time
start = time.time()

...

end = time.time()
print(f"{end - start:.5f} sec")

예제 입력

100000000 21
27
567
999
234
50
567
123
4734
754
84
35
1353
76
464
4634
65
89
3553
59
38
4135

출력

22640 # 답
2.14640 sec # 소요 시간

타임 오버가 뜨기 때문에 시간을 더 단축해보자

다른 풀이

# ✅ pSum(=partialSum): 지금까지 승차한 바둑이들 무게 합 
# ✅ vSum(=visitedSum): 승차 여부에 관계없이 방문(판단)한 바둑이들 무게 합
def DFS(idx, pSum, vSum):
    global mx
    # 지금까지 승차한 바둑이들 + (이후 모든 바둑이가 승차한다고 가정) 했을 때에도
    # 현재 mx 값보다 작다면 이후 바둑이들은 탐색할 필요가 없다
    if pSum + (tot - vSum) < mx:
        return # ✅ cut edge
    if pSum > C:
        return # ✅ cut edge
    if idx == N:
        if pSum > mx:
            mx = pSum
    else:
        DFS(idx+1, pSum+lst[idx], vSum+lst[idx]) # vSum에는 무조건 누적
        DFS(idx+1, pSum, vSum+lst[idx]) # vSum에는 무조건 누적

C, N = map(int, input().split())
lst = [int(input()) for _ in range(N)]

mx, tot = -1, sum(lst)
DFS(0, 0, 0)
print(mx)

시간 측정

이전과 동일한 방법으로 복잡한 입력으로 시간을 재보자.

22640
0.00038 sec # 소요 시간이 단축되었다!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기