DP, 격자 안에서 한칸씩 전진하는 DP

격자 안에서 한칸씩 전진하는 문제는 어떻게 풀까요~?~?

우리는 DP 시리즈 중 2번째 격자 안에서 한칸씩 전진하는 DP를 이제 풀게되었습니다. 

대표적인 알고리즘 문제중 정수 사각형 최대합or 최소합or 최솟값의 최대,   정수 사각형 최장 증가 수열, 사각형 차이의 최소, 등 2차원 배열의 최솟값, 최대값, 최장 증가 부분 수열(LIS라고들 하죠) 문제를 접했을때 푸는 문제입니다. 

 

2차원 배열을 이용하는거라 좀더 흥미가 있는데요 

이런 블럭이 존재했을때, 맨위에서 맨밑으로 내려왔을때 얻을수 있는 최대합은 무엇일까요? 에 대해서 문제 풀이를 진행해보도록하겠습니다. (이 때, 이동은 아래 혹은 오른쪽으로만 갈수있습니다)

 

우리가 생각한 문제접근의 반례

문제를 접하고 어? 그냥 큰값만 보면서 내려가면되는거아니야? 하고 문제를 접해보겠습니다.

큰 값만 내려가는 알고리즘 사용했을때

 

어라? 문제를 보다보니 왼쪽 사진처럼 큰수만 내려가다보면 오른쪽 사진만큼 값을 크게 못내게 됩니다.  그럼 우리는 도대체 어쩌라는거야? 라고 생각 하실수도있습니다. 저도 고민이 좀 되는데요 어떻게 해결해야할까요? DP라고 무조건 생각하지마시고 좀만 더 고민해보시죠 저도 같이 고민해보겠습니다. 사진 한장 드리겠습니다.

 

고민의 시간

 

합은 같지만 이동 방식이 다름

 

이럴수가, 두 값이 다르네요... 마지막행을 보겠습니다. 똑같은 합에서 4번째행에서 어떻게 진행해야하나? 라고 보여주고있는 것 같습니다. 똑같은 합에서 다음행으로 갔을때 우리는 무엇을 고려해야하나요? 

흠..좀 어렵네요 하지만 이 두 사진은 마지막으로 방문한 위치가 같고 이동한 경로상의 숫자 합이 일치합니다. 

"마지막으로 방문한 위치", "이동한 경로상의 숫자합"이 일치할때 우리는 어떤 선택을 해야하는지가 중요합니다. 이 4번째행이 아닌 1번째 행으로 간다면 똑같이 의미가 부여됩니다. "마지막으로 방문한 위치"이고 "이동한 경로상의 숫자 합"이 일치한다는거죠 

 

좋았어 뭘 좀알아냈는데?!

1. 마지막으로 방문한 위치가 같은가

2. 이동한 경로상의 숫자합이 누가 더 큰것인가? 

을 고려했을때, 1이 동일하다면 2를 고려하는 입장에서 더 큰것을 고려하는것이 맞겠죠? 무슨말인지 모르시겠다구요? 저도 잘 모르겠습니다.... 이동한 경로상의 숫자합을 누가 더큰지 내가 어떻게 알까요? 이것만 알수있다면 내가 해결할수 있을거 같은데 말이죠 1번은 확실히 알수있는데, 2번을 위해서 제가 마술을 한번 부려보겠습니다. 이름하여 미리미리 채워놓자 마술 !  우리는 운좋게도 맨밑으로 쭉 내려가는 놈과 맨 오른쪽만 가는놈의 합을 구할수있습니다.

 

맨밑만 맨오른쪽만 가는 녀석

이 놈들을 구하니까 여태까지의 이동한 경로상의 숫자합을 저 사이만 채우면된다고 생각하면됩니다. 

결국 내가 지금 있는 위치가 왼쪽에서 오는 놈이 더 큰지 내 밑에서 오는놈이 더 큰지 고려하면된다는겁니다 

 

DP[1,2] = 내 위치에서 왼쪽놈이 더 큰가요? 와 내 위치에서 윗놈이 더 큰가요?를 비교하시면 당연히 현재위치는 더 큰놈으로 Update 된다는것이죠 !!! 

 

아하 이거구나!

 

아하 이제 알았습니다. 마지막으로 방문한 위치가 같을때 이동한 경로상의 숫자합이 누가 더큰가는 다시 말해 내 현재 위치에서 여태까지 더해져 온애들에 대한 index를 고려해서 날 더 큰놈으로 만들면 되는 문제군요?

 

근데요...난 이런문제를 수도없이 보았지만 생각이 전혀 떠오르지 않는데요 ? 라고 생각할수도있습니다. 맞습니다 이런 문제를 유추하기에는 너무 어려운것이죠 그래서 이런문제들을 접했을땐 생각을 해보시면됩니다.  내가 더하는 다음놈이 큰지 안큰지 다다음놈이 큰지 안큰지 어떻게 알아? 했을때 내 현재위치에서 제일 큰놈만 가져오면 되지않을까? 란 발상희 전환을 말이죠 .

 

해당 문제의 점화식

이 문제에 대해서는 또 점화식이 필요하겠죠? 

DP[i][j] = max(dp[i-1][j] + a[i][j] , dp[i-1][j-1] +a[i][j]) 라는 점화식이 필요하게됩니다. 여기서 DP[i][j]는 메모이제이션이 되지않을까요? 히히 결국 우리는

이런 결과값을 얻게됩니다 !!! 이 결과값은 우리가 작은 문제가 먼저 풀려있다는 가정하에서 큰 문제를 푼것이비다. 

격자 안에서 한칸씩 전지하는 DP유형의 경우 위-> 아래, 왼쪽 -> 오른쪽 방향으로 for문을 진행하던 방향으로 진행하면 dp[i][j]는 더 작은 문제들이 풀여있는 상황에서 그 값을 이용해 원하는 결과를 계산할수있습니다!