사용자 도구

사이트 도구


ps:problems:boj:15645

내려가기 2

ps
링크https://www.acmicpc.net/problem/15645
출처BOJ
문제 번호15645
문제명내려가기 2
레벨실버 1
분류

DP

시간복잡도O(n)
인풋사이즈n<=100000
사용한 언어Python
제출기록29200KB / 276ms
최고기록276ms
해결날짜2021/12/11

풀이

  • 기초적인 DP 문제.
  • 3*N 크기의 dp 테이블을 채워 나가면 된다. 시간 복잡도는 O(n)
  • 슬라이딩 윈도우 기법을 적용하는 것도 가능하고 아래 코드도 그렇게 작성된 코드이지만, 이 문제에서는 굳이 안쓰더라도 상관은 없다. 슬라이딩 윈도우를 반드시 사용해야만 풀리도록 만든 문제는 내려가기이다.

코드

"""Solution code for "BOJ 15645. 내려가기 2".

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

Tags: [DP]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    min_l = min_m = min_r = max_l = max_m = max_r = 0
    for _ in range(N):
        l, m, r = [int(x) for x in sys.stdin.readline().split()]
        min_l, min_m, min_r = (min(min_l, min_m) + l,
                               min(min_l, min_m, min_r) + m,
                               min(min_m, min_r) + r)
        max_l, max_m, max_r = (max(max_l, max_m) + l,
                               max(max_l, max_m, max_r) + m,
                               max(max_m, max_r) + r)

    print(max(max_l, max_m, max_r), min(min_l, min_m, min_r))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
G I M V R
 
ps/problems/boj/15645.txt · 마지막으로 수정됨: 2021/12/11 14:11 저자 teferi