내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
내려가기 2
ps:problems:boj:15645
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 내려가기 2 ====== ===== 풀이 ===== * 기초적인 DP 문제. * 3*N 크기의 dp 테이블을 채워 나가면 된다. 시간 복잡도는 O(n) * 슬라이딩 윈도우 기법을 적용하는 것도 가능하고 아래 코드도 그렇게 작성된 코드이지만, 이 문제에서는 굳이 안쓰더라도 상관은 없다. 슬라이딩 윈도우를 반드시 사용해야만 풀리도록 만든 문제는 [[ps:problems:boj:2096]]이다. ===== 코드 ===== <dkpr py> """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() </dkpr> {{tag>BOJ ps:problems:boj:실버_1}}
ps/problems/boj/15645.txt
· 마지막으로 수정됨: 2021/12/11 14:11 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로