백준 2096 (내려가기)

백준 2096 (내려가기)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/2096

문제 접근

유사한 문제 : 백준 1149 (RGB거리) 유사한 문제 : 백준 17404 (RGB거리 2)

반갑습니다. 어렸을 때 땅따먹기 했던 생각이 나서 들고온 문제입니다. nx3의 board에서, 내가 i번째 row에 있다면 다음 번엔 현재 위치 바로 아래 or 현재 위치 바로 아래와 붙어 있는 위치로 이동할 수 있는 문제입니다. 마지막 단계에서 최댓값과 최솟값을 구하는 문제입니다. 딱 봐도 이제 동적계획법 문제로 보입니다.

이런 형태로 가능하다는 의미입니다!

제가 딱 봐도 dp 문제라고 하지만, 당연한 것을 당연하게 이야기를 할 줄 알아야, 진짜 당연한 것이라고 생각합니다. 즉 말로 설명을 할 줄 알아야 아는 것이라고 생각합니다. 설명해보자면, 나의 현재 상태는 내가 몇 번째 row에 있는지, 몇 번째 col에 있는지에 따라서 선택됩니다. 예전에 어떻게 움직였는지는 중요한 사항이 아닙니다. 나는 바로 직전의 상태만 알면 되기 때문입니다. 그렇다면 내가 직전 상태를 잘 메모만 해둔다면, 쉽게 해결할 수 있을 것 같습니다. 즉, 동적 계획법 문제입니다.

너무 동적 계획법 문제만 하는 것 같아요. 제가 graph쪽과 greedy(유감스럽게도 다 g씨인 ..)유형이 조금 약한 듯 해보입니다. 앞으로는 약점을 보완을 잘 해야겠어요.

아무튼, 게임판을 board 2차원 배열로 nx3 배열로 나타내려고 했지만, 문제의 제한 조건이 조금 까다롭습니다. 바로 메모리 제한이 4MB로 걸려 있다는 것입니다. 4MB면 4x10^6 byte고, 대충 정수 하나당 4byte를 사용하고, pypy3이나 python을 사용해서 dp_max[n][3], dp_min[n][3]을 선언한다면 메모리 관리가 조금 어려워 보입니다. 또 메모리는 돈이기에, 아끼면 아낄수록 좋다고 생각합니다. 너무 자본주의적 사고인가요? 아무튼 자원은 아끼면 아낄수록 좋다고 생각합니다. 전기든 물이든 뭐든 . . 각설하고 문제를 해결해봅시다.

배열을 선언하는 것은 좀 무거워 보이는데, 굳이 배열을 선언할 필요가 사실 없다고 생각합니다. 0/1 knapsack problem도 2차원 dp[item수][weight] 크기의 배열을 선언하지만 사실 할 필요가 없습니다. i번째 단계에서 필요한 것은 i-1번째 단계의 값들만 필요한 것이니까요.

그렇다면 그냥 2차원 배열을 선언하지 않고, 직전 상태만 저장해두는 1차원 배열을 선언해서 해결하자는 것이 문제의 사고과정입니다. 그렇다면 dp_max 배열과 dp_min 배열을 내가 i번째 단계일 때, i-1번째 단계에서의 최댓값과 최솟값을 갖도록 구현하자는 것이 저의 아이디어입니다. 점화식으로 나타내보자면,

zero, one, two = dp_max[0], dp_max[1], dp_max[2]
dp_max[0]=max(zero, one)+board[0] 
dp_max[1]=max([zero, one, two])+board[1] 
dp_max[2]=max(one, two)+board[2] 
zero, one, two = dp_min[0], dp_min[1], dp_min[2]
dp_min[0]=min(zero, one)+board[0] 
dp_min[1]=min([zero, one, two])+board[1] 
dp_min[2]=min(one, two)+board[2] 

로 나타낼 수 있겠습니다. 그냥 직접 나타냈습니다.

소스 코드

import sys
n=int(input())
board=[]
dp_max, dp_min =[] , []
for i in range(n) :
    board=list(map(int,sys.stdin.readline().split()))
    if i==0 :
        dp_max=board[:]
        dp_min=board[:]
    else:
        zero, one, two = dp_max[0], dp_max[1], dp_max[2]
        dp_max[0]=max(zero, one)+board[0] 
        dp_max[1]=max([zero, one, two])+board[1] 
        dp_max[2]=max(one, two)+board[2] 
        zero, one, two = dp_min[0], dp_min[1], dp_min[2]
        dp_min[0]=min(zero, one)+board[0] 
        dp_min[1]=min([zero, one, two])+board[1] 
        dp_min[2]=min(one, two)+board[2] 
    
print(max(dp_max))
print(min(dp_min))       

마무리하며

동적계획법 문제입니다. 다음 시간엔 애드 혹 문제를 반드시 포스팅하는걸로!