[백준] 2096번 내려가기
11106 단어 다이나믹 프로그래밍다이나믹 프로그래밍
문제 링크
https://www.acmicpc.net/problem/2096
문제 설명
- 3 x n board에서 내려가면서 최댓값, 최솟값 구하기
풀이
접근
- 처음에 간단한 DP라고 생각했다
난관1
- 그대로 구현하니 메모리 초과가 났다
- 살짝 멘붕올뻔 했지만 마음을 가다듬고 생각해봤다
- 처음에 n x 3이 아니라 n x 1 크기로 만들어볼까 했지만 이전 경로도 알아야 되기 때문에 그건 안 된다는걸 알았다
해결
- DP 리스트를 생각해보니 바로 이전 값들만 참조하면 되기 때문에 굳이 n개만큼 만들 필요가 없었다
- 2 x 3을 두 개 만들어서 계산해주고 위치 바꿔주는 식으로 했다
난관2
- 근데 마지막에 100프로에서 또 오답나와서 혼란스러웠다
해결
- 질문들을 보다가 n이 1일 경우에 오답이란걸 알았다
코드
import sys
read = sys.stdin.readline
n = int(read())
board = [list(map(int, read().split())) for _ in range(n)]
dp_max = [board[0], [0,0,0]]
dp_min = [board[0], [0,0,0]]
for y in range(1, n):
dp_max[1][0] = max(dp_max[0][0], dp_max[0][1]) + board[y][0]
dp_max[1][1] = max(dp_max[0]) + board[y][1]
dp_max[1][2] = max(dp_max[0][1], dp_max[0][2]) + board[y][2]
dp_max[0] = dp_max[1][:]
dp_min[1][0] = min(dp_min[0][0], dp_min[0][1]) + board[y][0]
dp_min[1][1] = min(dp_min[0]) + board[y][1]
dp_min[1][2] = min(dp_min[0][1], dp_min[0][2]) + board[y][2]
dp_min[0] = dp_min[1][:]
print(max(dp_max[0]), min(dp_min[0]))
Author And Source
이 문제에 관하여([백준] 2096번 내려가기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-2096번-내려가기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
read = sys.stdin.readline
n = int(read())
board = [list(map(int, read().split())) for _ in range(n)]
dp_max = [board[0], [0,0,0]]
dp_min = [board[0], [0,0,0]]
for y in range(1, n):
dp_max[1][0] = max(dp_max[0][0], dp_max[0][1]) + board[y][0]
dp_max[1][1] = max(dp_max[0]) + board[y][1]
dp_max[1][2] = max(dp_max[0][1], dp_max[0][2]) + board[y][2]
dp_max[0] = dp_max[1][:]
dp_min[1][0] = min(dp_min[0][0], dp_min[0][1]) + board[y][0]
dp_min[1][1] = min(dp_min[0]) + board[y][1]
dp_min[1][2] = min(dp_min[0][1], dp_min[0][2]) + board[y][2]
dp_min[0] = dp_min[1][:]
print(max(dp_max[0]), min(dp_min[0]))
Author And Source
이 문제에 관하여([백준] 2096번 내려가기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-2096번-내려가기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)