[백준] 14501 퇴사 (by Python)

문제(실버3)

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

14501번: 퇴사

문제 설명

최대 수익 구하는 문제

조건에 맞는 최대 값 구하는 문제 -> DP 떠올리기!

 

이 문제는 정해진 n날짜를 넘어가는 경우에는 해당 날짜 수업을 하지 못하므로 뒤에서 부터 dp값을 정해줬다

뒤에서 부터 "상담 안 할 경우(이전 값)와 상담 할 경우(상담하게되면 종료 시점 날의 dp값 + 상담 날 이익)" 중 큰 값으로 설정

 

풀이 1) 뒤에서 부터 dp 적용할 경우

# 목표) 최대 수익 구하기
# dp
n = int(input())
li = []
dp = [0] * (n+1) # 맨 마지막 값도 동일한 로직을 적용하기 위해서 n+1 크기로 초기화

for _ in range(n):
    t, p = map(int, input().split())
    li.append([t, p])

# 뒤에서 부터
for i in range(n-1, -1, -1): # n-1부터 0까지
    if i + li[i][0] > n: # n일을 넘어갈 경우
        dp[i] = dp[i+1] # 이전 값으로 설정
    else:
        # 오늘 상담 안할경우([이전 이익])와 상담 할 경우([li[i][0]일 후 이익 + (i+1)일의 이익] 중 큰 값으로 설정)
        dp[i] = max(dp[i+1], dp[i + li[i][0]] + li[i][1])

    #print(dp)

print(dp[0])

풀이 2) 앞에서부터 dp 적용할 경우

 

# 목표) 최대 수익 구하기
# dp 

n = int(input())

li = []  
dp = [0] * (n+1) 

for _ in range(n):
    a, b = map(int, input().split())
    li.append([a, b])
 
for i in range(len(li)):
    for j in range(i+li[i][0], len(li)+1): # 수업 끝난 이후부터 확인
        if dp[j] < dp[i]+li[i][1]: # i+1일에 상담하는 것의 이득이 더 클경우
            dp[j] = dp[i]+li[i][1] 
    print(dp)

print(dp[-1])

풀이2가 아주 조금 빠르긴 한데 의미없다 ㅋ.ㅋ