사용자 도구

사이트 도구


ps:problems:boj:15486

퇴사 2

ps
링크https://www.acmicpc.net/problem/15486
출처BOJ
문제 번호15486
문제명퇴사 2
레벨실버 1
분류

DP

시간복잡도O(n)
인풋사이즈n<=1,500,000
사용한 언어Python
제출기록95824KB / 2032ms
최고기록1632ms
해결날짜2022/02/05

풀이

  • 퇴사에서 n의 범위를 늘린 버전. 풀이는 그쪽을 참고.

코드

"""Solution code for "BOJ 15486. 퇴사 2".

- Problem link: https://www.acmicpc.net/problem/15486
- Solution link: http://www.teferi.net/ps/problems/boj/15486

Tags: [DP]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    dp = [0] * (N + 1)
    for i in range(N):
        t_i, p_i = [int(x) for x in sys.stdin.readline().split()]
        if dp[i] > dp[i + 1]:
            dp[i + 1] = dp[i]
        if i + t_i <= N and dp[i] + p_i > dp[i + t_i]:
            dp[i + t_i] = dp[i] + p_i
    print(dp[N])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
H U A G B
 
ps/problems/boj/15486.txt · 마지막으로 수정됨: 2022/02/05 16:16 저자 teferi