[백준] 14501(파이썬) - 퇴사

www.acmicpc.net/problem/14501

14501번: 퇴사

 

구현 감각을 익히기 위해 전에 풀었었던 삼성 코테 기출문제를 다시 풀고 있습니다. 다시 풀어보니 꽤 생각을 많이 하게 되더라고요.

 

• 이 문제는 아주 친절하게 표를 줬습니다. 주어진 표를 보니 DP 생각이 떠오르더군요. 바로 DP 풀이 가겠습니다.
• 먼저 구하려는 값인 최대 이익을 담을 dp 리스트, 그리고 필요한 기간이 담긴 t 리스트, 얻을 수 있는 이익이 들어있는 p 리스트를 n+1 개만큼 0으로 초기화해서 만들어줍니다.
• 그다음, 주어진 표대로 값을 넣어주기 위해 for문을 돌리면서 t[i], p[i]에 입력되는 데이터를 받아서 넣어줍니다.
• 이제 문제해결을 위한 핵심 구현을 해보겠습니다.
  고민을 하다가 n 일을 넘기지 않도록 최댓값을 구해야 하기 때문에 역순으로 for문을 돌려줬습니다.
  필요한 기간 + 현재 일이 주어진 n 미만일 경우, dp[i] 값을 갱신해줬습니다.

 

# dp를 이용하는 문제

import sys
input = sys.stdin.readline


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

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

for i in range(n):
    t,p = map(int,input().split())
    T[i] = t
    P[i] = p

for i in range((n+1)-2,-1,-1):
    if T[i] + i <= n:
        dp[i] = max(dp[i+1],P[i]+dp[i+T[i]])
    else:
        dp[i] = dp[i+1]

print(dp[0])