[Baekjoon] 14501. 퇴사 [S3]
📚 문제
https://www.acmicpc.net/problem/14501
📖 풀이
재귀를 활용한 DFS로 해결하는데 조합을 활용한다.
상담을 고르는 것과 고르지 않는 것!
날짜만큼 진행시켜주니 백트래킹이라 할 수 있다.
재귀 호출할 때 상담의 날짜를 담아 호출하고, 날짜를 넘어가면 종료시킨다.
끝까지 갔을 때 최대 수익을 갱신한다.
하루에 상담일정이 하나씩 있으니 고르는 거와 안 고르는 걸로 조합으로 재귀 호출한다.
일정이 n에 도착하면 최댓값을 갱신하고 n을 넘어가면 상담 일정이 초과하는 것이니 버린다.
📒 코드
def recur(day, p):
global result
if day > n:
return
if day == n:
result = max(result, p)
return
recur(day + 1, p)
recur(day + arr[day][0], p + arr[day][1])
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
result = 0
recur(0, 0)
print(result)
🔍 결과
Author And Source
이 문제에 관하여([Baekjoon] 14501. 퇴사 [S3]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/Baekjoon-14501.-퇴사-S3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)