[백준] 14501번 퇴사

사용 언어 - Python3

문제 -  14501번 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

 

정답

1. 완전 탐색적 재귀함수

def recur(day, total)

recur(상담받는 날짜, 수익합)

day = 0일부터 n-1일까지 반복

day가 n-1보다 크고, n보다 크면 무시

아니라면, total,answer 중 더 큰 수익값으로 업데이트

 

- 상담 하는 경우, 날짜+날짜만큼 더하기, 수익+수익만큼 더하기

- 상담 안하는 경우, 날짜+1, 수익 그대로

 

print(answer)

def recur(day,total):
    global answer
    if day > n-1: # day = 0일부터 n-1일까지
        if day > n: return
        answer = max(total,answer)
        return
    
    # 상담 하는 경우
    recur(day+list_a[day][0],total+list_a[day][1])
    # 상담 안하는 경우
    recur(day+1, total)

n = int(input()) # n일째
list_a = [list(map(int,input().split())) for _ in range(n)] # t,p
answer = 0
recur(0,0) #0일부터 시작
print(answer)

 

2. 탑다운 DP(메모이제이션)

기억 = 효율 증가

1일을 선택하면, 수익합 10

경우1) 5일을 선택 -> 7일차에는 항상 상담을 받는 게 좋다. 수익합 10+15+200

경우2) 항상 6일차에 받는 게 좋다. 수익합 10+40

-> 항상 7일차에 받는 게 좋다. 수익합이 더 크니까! 

-> 뒤에서부터 값 기억해주자

이미 계산된 내용을 기억하고, 마지막 값만 바꾸자!!!

한번만 전체 다 계산해주면, 다신 연산할 필요가 없다.

 

dp 라는 빈 리스트 만들어주기

dp[day]에 뒤에서부터 상담 받거나/안받거나 둘중 수익이 더 큰 경우를 저장해준다.

- 상담 받는 경우의 수익

recur(day+해당 날짜) + 해당 수익

- 상담 안받는 경우의 수익

recur(day+1)

return dp[day]

 

- 만약, 이미 dp[day] 값이 있다면, 또 계산하지 말고 dp[day] 사용해라

- day가 n을 초과하면 -999999999

- day가 n을 모두 다했다면 0

import sys
sys.setrecursionlimit(99999999)
input = sys.stdin.readline

def recur(day):
    if day > n: # day = 0일부터 n-1일까지
        return -9999999999999
    if day == n:
        return 0
    
    # 이미 저장되었다면
    if dp[day] != -1:
        return dp[day]
    
    # 상담 받거나/안받거나 둘중 더 많은 돈을 버는 경우를 내 dp 테이블에 저장
    dp[day] = max(recur(day+list_a[day][0]) + list_a[day][1],recur(day+1))    
    return dp[day]

n = int(input()) # n일째
list_a = [list(map(int,input().split())) for _ in range(n)] # t,p
dp = [-1 for _ in range(n+1)]
recur(0) #0일부터 시작
print(dp[0])

 

3. 바텀업 DP

탐다운을 for문으로 만들어주면 점화식 도출된다.

n = int(input()) # n일째
list_a = [list(map(int,input().split())) for _ in range(n)] # t,p

dp = [0 for _ in range(n+1)]

for idx in range(n)[::-1]:
    if (idx+list_a[idx][0]) > n: # 범위 초과시
        dp[idx] = dp[idx+1]
    else:
        dp[idx] = max(dp[idx+list_a[idx][0]]+list_a[idx][1],dp[idx+1])
print(dp[0])

 

 

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/14501_%ED%87%B4%EC%82%AC.py

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/14501_%ED%87%B4%EC%82%AC2.py

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/14501_%ED%87%B4%EC%82%AC1.py