[백준] 14501번 퇴사 (Python)

14501번: 퇴사

백준 14501번: 퇴사 문제 설명

백준 14501번 퇴사: 입출력 및 예제

 

---

문제 풀이

참고로 해당 문제는 삼성 SW 역량 테스트 기출문제로 분류되어 있고 solved.ac기준 실버 III 난이도다

예제 입력1을 기준으로 천천히 생각해보자

첫째 날에 상담을 할 수도 안 할 수도 있다

• 상담을 한다면: 10만큼의 금액을 벌고 3일 뒤에 다시 상담 여부를 결정한다
• 반대로, 상담을 안 한다면: 0의 금액을 벌고 그다음 날에 상담 여부를 결정한다
• 이런 식으로 N만큼의 날짜가 흐를 동안 벌 수 있는 금액 중 최댓값을 구하면 된다

위 로직에 따라 DFS를 활용하면 문제를 해결할 수 있다

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
t = []
p = []
arr = []

for i in range(n):
    ti, pi = sys.stdin.readline().rstrip().split()
    t.append(int(ti))
    p.append(int(pi))

def dfs(day, earn):
    if day >= n:
        arr.append(earn)
        return
    #현재 day + 소요 day가 n보다 크면 상담을 하지 않는 조건을 붙여준다
    if (day+t[day]) <= n:
    	#현재 day에서 상담을 진행하는 경우
        dfs(day+t[day], earn+p[day])
    #현재 day에서 상담을 진행하지 않는 경우
    dfs(day+1, earn)

dfs(0, 0)
print(max(arr))

 

GitHub에서 코드 보기