[Python/BOJ] 30621. 어? 금지

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

30621번: 어? 금지

문제

'어?'

팀 대회 중 주변에서 '어?'라는 말이 들리면 마음이 혼란해진다. 그렇다고 해서 '어?'를 남발하면 혼란보다는 짜증이 앞서게 된다. 이를 잘 알고 있는 성우는 적당한 선을 지키면서 대회장에 최대한 큰 혼란을 주려고 한다.

• 대회는 시각 0에 시작한다.
• 성우가 '어?'를 외칠 수 있는 시각은 N개가 있고, i번째 시각은 t_i다. (1≤i≤N)
• 만약 성우가 시각 t_i에 '어?'를 외치려 한다면, 성우는 시각 (t_i - b_i)부터 지금까지 '어?'를 외친 적이 없어야 한다.
  • 성우가 정확히 시각 (t_i - b_i)에 '어?'를 외쳤더라도 시각 t_i에 '어?'를 외칠 수 없다.

성우가 시각 t_i에 '어?'를 외치면 대회장에 c_i만큼의 혼란이 가해진다. 최종 혼란은 대회장에 가해진 혼란의 합이다.

성우는 대회장에 줄 수 있는 최종 혼란의 최댓값이 궁금해졌다. 성우를 위해 이를 구해주자.

입력

첫 번째 줄에 성우가 '어?'를 외칠 수 있는 시각의 개수 N이 주어진다. (1≤N≤100000)

두 번째 줄에 정수 t_1, t_2, ⋯, t_N이 공백을 사이에 두고 주어진다. (1≤ t_i ≤10^9 ;  t_i-1 < t_i )

세 번째 줄에 정수 b_1, b_2, ⋯ , b_N이 공백을 사이에 두고 주어진다. (1≤b_i≤109 ; b_i≤t_i)

네 번째 줄에 정수 c_1, c_2, ⋯, c_N이 공백을 사이에 두고 주어진다. (1≤c_i ≤10^9)

출력

첫 번째 줄에 성우가 대회장에 줄 수 있는 최종 혼란의 최댓값을 출력한다.

풀이

Code

import sys
from bisect import bisect_left
input = sys.stdin.readline

def solution(n, time, blank, cost) :
    # 1. 시각, 혼란값 dp 생성
    dp = [0 for _ in range(n+1)]
    # 2.
    for i in range(1, n+1) :
        t, b, c = time[i], blank[i], cost[i]
        # 2-1. t - b초 직전의 초에 해당하는 인덱스 값 찾기
        idx = bisect_left(time, t-b) - 1
        # 2-2. 점화식에 따라 최대 혼란값 생성
        dp[i] = max(dp[i-1], dp[idx] + c) if idx >= 0 else max(dp[i-1], c)
    # 3. 결과 출력
    print(dp[-1])

if __name__ == "__main__" :
    n = int(input())
    time = [0] + list(map(int, input().split()))
    blank = [0] + list(map(int, input().split()))
    cost = [0] + list(map(int, input().split()))
    solution(n, time, blank, cost)