BOJ 14501 퇴사

LONGNEW·2021년 3월 1일
0

BOJ

목록 보기
186/333

https://www.acmicpc.net/problem/14501
시간 2초, 메모리 512MB
input :

  • N (1 ≤ N ≤ 15)
  • Ti Pi(1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

output :

  • 백준이가 얻을 수 있는 최대 이익을 출력

역시 봤었던 문제가 제일 문제인 것 같다 ㅋㅋㅋㅋㅋㅋㅋㅋ
앞에서 부터 할 경우 사용하는 변수가 매우 많아질 것 같고 중간에 겹치는 부분을 계산해 줘야 한다.

뒤에서 부터 계산을 하는 것이 편하다.
두가지 조건이 생기는 데.
1. 현재 상담을 수행할 경우 퇴사 날짜를 지나 버릴 때 .
2. 현재 상담을 수행할 수 있다. (여기에서 다시 2가지. - 현재 상담을 수행하는 것이 이득인지, 아니면 하지 않는 것이 나은지)

이 2. 의 경우를 보기 위해서 1번 예시를 보는 것이 가장 이해 하기 쉽다.

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

위의 예시에서 index 2번 5 20 을 보면
그 이전까지의 최대값은 45 이다. index 3, 4, 5를 다 수행한 경우
그리고 index 2번을 수행 할지 말지를 생각해야 하는데

수행 한다면 20 + data[index(2) + 5] 번째의 값을 얻게 된다.
수행 하지 않은 경우엔 지금까지의 최댓값 45를 받아온다.

그래서 이 둘의 max값을 비교해주는 것이다.

언제나 이런 포인터가 애매해지는 경우에는 뒤에서 부터 시작하는 경우가 많은 것 같다.

import sys

n = int(sys.stdin.readline())
data = [[0] * n for i in range(2)]

for i in range(n):
    t, p = map(int, sys.stdin.readline().split())
    data[0][i] = t
    data[1][i] = p

dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    if i + data[0][i] > n:
        dp[i] = dp[i + 1]
    else:
        dp[i] = max(dp[i + 1], data[1][i] + dp[i + data[0][i]])
print(dp[0])

0개의 댓글