[백준]_2096번 : 내려가기(파이썬)

2096번: 내려가기

반응형

비슷한 문제로는 RGB 거리 문제가 떠오른다. 전형적인 DP문제로 쉽게 풀 것이라고 생각했지만 모든 dp문제가 다 그렇듯이 문제마다 요구하는 특별한 방법이 있기 때문에 상황 파악이 우선이다. 필자는 이 문제를 풀 때 잘못된 접근을 하여 한동안 헤맸었다. 잘못된 접근 법은 아래에 정답 코드 이후에 설명하겠다.

 

접근

문제의 조건을 보면 N이 100000까지 커질 수 있기 때문에 2차원 dp N*3짜리를 만드는 것은 별로 효율적이지 않다. 따라서 dp리스트는 3*1짜리로만 풀 것이고 새로운 입력을 받을 때마다 dp를 업데이트시켜줄 것이다. 예를 들어 예제 1과 같은 입력을 받았다고 생각해 보자(최대 값을 구하는 방법으로 한정해서 생각해 보자). 

3
1 2 3
4 5 6
4 9 0

먼저 dp에 [1 2 3]을 넣어준다. 

 

그다음에 [4 5 6] 을 입력받은 후 이 리스트를 ls라고 칭하겠다. 이제 아래와 같은 방식으로 화살표를 따라 최댓값 연산을 해주면 된다.

이 과정을 N-1회 해주면 된다.

시도 1(Python)

import sys

input = sys.stdin.readline

n = int(input())
ls = list(map(int, input().split()))
dp_max = ls[:]
dp_min = ls[:]
for i in range(1, n):
    ls = list(map(int, input().split()))
    ls2 = ls[:]
    ls[0], ls[1], ls[2] = ls[0] + max(dp_max[0], dp_max[1]), ls[1] + max(dp_max), ls[2] + max(dp_max[2], dp_max[1])
    dp_max = ls[:]
    ls = ls2[:]
    ls[0], ls[1], ls[2] = ls[0] + min(dp_min[0], dp_min[1]), ls[1] + min(dp_min), ls[2] + min(dp_min[2], dp_min[1])
    dp_min = ls[:]
print(max(dp_max), min(dp_min))

---

잘못된 접근 방법

위에서는 아래의 ls값에서 그 이전 입력(dp)에 접근했었다면 이번에는 반대로 dp값을 기준으로 ls로 내려가보자. 이렇게 되면 문제가 하나 생긴다.

오른쪽 그림과 같이 왼쪽 끝은 절대 오른쪽 끝을 건드리지 못하기 때문에 잘못된 결과물로 이어질 수도 있다.