[김태원 알고리즘] 휴가 (DFS)

사용 언어: Python3

문제

풀이

내 풀이 - 경로(path) 저장 O

def DFS(L, price):
    global mx
    if L >= N:
        sm = 0
        for x in path:
            sm += x[1]
        mx = max(mx, sm)
    else:
        path.append(lst[L])
        DFS(L+lst[L][0], price+lst[L][1]) # 상담 O
        
        path.pop()
        DFS(L+1, price) # 상담 X

N = int(input())
lst = list()
for _ in range(N):
    T, P = map(int, input().split())
    lst.append((T, P))

path = []

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

• 선택한 노드(경로)를 저장하여 푸는 방법이다.
• 정답!
  • 복잡한 예제까지 통과한다.

내 풀이 - 경로(path) 저장 X

def DFS(L, price):
    global mx
    if L > N:
        return
    elif L == N: # 종료
        mx = max(mx, price)
    else:
        DFS(L+lst[L][0], price+lst[L][1]) # 상담 O
        DFS(L+1, price) # 상담 X

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

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

• 경로를 굳이 저장할 필요는 없으므로 이 풀이가 더 좋은 풀이인 것 같다.
• 정답!
  • 복잡한 예제까지 통과한다.

---

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

맨 위로 이동하기