[Python] 14501번 퇴사, 그림 설명, 자세한 설명

✏️ 문제

 

문제 파악

처음에는 시작점을 기준으로 잡아서 풀려고 했는데 경우의 수가 너무 많았다...!  

뭔가 2156번 포도주 문제랑 2579번 계단 오르기 문제랑 비슷할 것 같아서 시간을 좀 썼는데 결국 못풀었다 ㅠ.. 아쉽

 

이 문제의 포인트는 시작점이 아닌 "끝점"을 기준으로 푸는 것이 포인트이다!

끝점부터 시작점까지 내려오는데 해당 위치에 있을 때 

• n일 때 상담한다.
• n일 때 상담하지 않는다.

이 두 가지 경우로 나누어서 둘 중에 더 큰 값을 dp[n]에 대입해야 한다.

n일 때 상담하지 않는 경우를 왜 고려하냐면

1. n일 때 상담하지 않고 n-1일 때 상담했을 때 (n-1일 때 t[n-1]이 2 이상일 경우) 더 이득일 경우도 있기 때문이다.
2. 무조건 n일 때 꼭 상담하라는 말이 없기 때문이다.

그림으로 작성하면 다음과 같이 나온다.

dp 의 위 배열은 n일 때 상담을 하는 경우 금액을 작성한거고 아래 배열은 n일 때 상담을 안하는 경우 금액을 작성했다.

대신 다음 위치(n-1)로 갈 땐 최대 이익을 구하기 때문에 두 값 중 max 값을 올려 계산하도록 했다. 

 

알고리즘 상 브루트포스 알고리즘으로도 풀 수 있는 거 같은데 현재 DP를 공부 중이기 때문에 DP 풀이만 작성했다.

 

 

알고리즘

• 다이나믹 프로그래밍 
• 브루트포스 알고리즘

 

코드

n = int(input())
t = [0] * n
p = [0] * n
dp = [0] * (n+1)

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

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

print(dp[0])