[BOJ] Q14501 퇴사

[BOJ] Q14501 퇴사

Question

Language: Python

Difficulty: Silver 3

각 날에 대해서 상담을 진행했을 때와 안 했을 때를 보면서 최대 보상을 구해야한다. 위 문제의 Time, Prize는 아래와 같다. ||||||||| |–|–|–|–|–|–|–|–| |Index|1|2|3|4|5|6|7| |T_i|3|5|1|1|2|4|2| |P_i|10|20|10|20|15|40|200|

다음과 같이 상담을 진행했을 경우, 만약 기존에 받을 수 있었던 보상보다 높은 경우를 이를 대체하고, 그렇지 않은 경우 그대로 둔다. 또한 상담을 진행하지 못하는 경우, 이때 까지 받을 수 있는 최대 보상값을 기입한다. |Index|1|2|3|4|5|6|7|Max_Prize| |–|:–:|:–:|:–:|:–:|:–:|:–:|:–:|:–:| |1일날 상담 진행시|0|0|10|||||10| |2일날 상담 진행시|0|0|10|||20||20| |3일날 상담 진행시|0|0|10|10||20||20| |4일날 상담 진행시|0|0|10|10+20||20||30| |5일날 상담 진행시|0|0|10|10+20|10+20+15|20||45| |6일날 상담 불가|0|0|10|10+20|10+20+15|45||45| |7일날 상담 불가|0|0|10|10+20|10+20+15|45|45|45|

maxPrize을 유지하므로써 중간 연산을 생략할 수 있다.

Solution

def solution():
    dp=[0] * (n)
    maxPrize=0
    for i in range(0,n):
        maxPrize=max(maxPrize,dp[i])
        if i + time[i] <n:
            dp[i+time[i]]=max(dp[i+time[i]],maxPrize+prize[i])
    
    return maxPrize

if __name__ == "__main__":
    n=int(input())
    times=[]
    prizes=[]

    for _ in range(n):
        time,prize=map(int,input().split())
        times.append(time)
        prizes.append(prize)
    print(solution())