[BOJ] 2096 내려가기

문제 링크

[BOJ] 2096 내려가기

출처 : https://www.acmicpc.net/problem/2096

문제 요약

- N개의 줄에 3개의 숫자를 입력받는다.

- 위에서부터 한 줄에 한 개의 숫자를 선택한다.

- 단 다음 줄에서 숫자를 선택하기 위해선 이전 숫자와 같은 열(j)이거나 양 옆의 열(j-1, j+1) 이어야 한다. 

- 선택한 숫자를 모두 더했을 때 최대, 최소 점수를 구하여라.

입출력

입력 

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

문제 해설

이 문제를 처음 봤을 때 한 줄에 입력 값이 3개 뿐이네 하고 쉽게 생각했다가 N의 최대가 100,000을 보고 당황했을 것이다.

모든 경로를 다 확인할 경우의 시간 복잡도는 최악의 경우 O(3^N)이 될 수 있다. 

(1줄에서 선택할 수 있는 경우의 수 X 2줄에서 선택할 수 있는 경우의 수 X ... N줄에서 선택할 수 있는 경우의 수)

시간을 줄이기 위해 상태 값을 저장하는 다이나믹 프로그래밍(DP) 방법을 이용하였다.

이 문제는 친절하게도 경로를 이동할 수 있는 조건을 그림으로 나타내었다.

위 별이 그려진 위치를 ( i, j ) 라 하였을 경우 다음 경로로 내려갈 수 있는 위치는 ( i+1, j-1 ), ( i+1, j ), ( i+1, j+1 ) 이다.

이를 반대로 본다면 ( i, j ) 위치를 선택하여 내려올 수 있는 이전 줄의 숫자 위치는  ( i-1, j-1 ), ( i-1, j ), ( i-1, j+1 ) 이다.

여기서 현재 위치 (i, j)에서 최소 점수를 가지려면 이전 줄에서 역시 누적된 최소 점수를 가져야 할 것이다. (최대 점수도 동일)

이를 수식으로 정의한다면 

  dp[i][j] = num[i][j] + min( dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1] )   

을 얻을 수 있다. ( dp  : 각 위치의 최소 누적 점수, num  : 해당 위치의 숫자)

이에 대한 시간 복잡도를 구하면 dp[N][3]의 상태값을 모두 구해야하므로  O(NX3) => O(N)을 얻을 수 있다.

여기에 슬라이딩 윈도우와 같은 개념을 이용한다면 메모리를 더욱 아낄 수 있다.

현재 i 줄의 위치에서 필요한 값은 이전 줄(i-1)의 값이다. (그 다음 줄(i+1)은 i 줄의 값만 필요하다. 결국 현재 위치에서 이전 줄 외의 정보는 불필요하다.)

이를 이용하면 해당 줄의 입력 값을 받으면서 값을 구할 수 있다.

  curr[j] = num[j] + min(before[j-1], before[j] , before[j+1])  

 그 다음 줄로 넘어갈 경우 현재 값은 이전 값으로 변경한다.

  before[j] = curr[j]  

이의 공간 복잡도를 구하면 이전 dp[N][3]의 O(NX3)에서 cur[3]+before[3]의 공간인 O(3X2) => O(1)으로 줄어든 상수 공간 복잡도를 가질 수 있다.

소스 코드

해당 수식을 코드로 표현하면 다음과 같다.

최대, 최소를 한번에 구하기 위해 curr, before 배열에 Pair를 이용하여 최소, 최대 정보를 동시에 저장하도록 하였다.

gist : https://gist.github.com/vinus322/088734e13701897e43cbd5095844c0d7