[ DP ] 조약돌 놓기(C++)

 

문제를 먼저 해석 해 보자. 3XN 테이블에는 양 또는 음의 정수가 주어진다. 각 열에는 적어도 1개의 조약돌을 놓아야 하며, 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다. 구해야 하는 것은 돌이 놓은 자리에 있는 수의 합을 최대가 되로고 하는 것이다. 

 

결국 최대 비용 문제이다. 그리고, 이전 $i$번째 열에 놓을 수 있는 조약돌의 위치는 이전 열에 영향을 받기 때문에 Dynamic Programming으로 접근하여 재귀식을 도출해야 한다. 

 

그렇다면 각 열에 놓을 수 있는 조약돌의 경우의 수는 뭘까?

 

 

위와 같이 총 4가지 경우의 수가 있다. 이를 각가 C1,2,3,4라 하자. 그렇다면 각 경우가 인접할 수 있는 경우의 수는 어떻게 될까? 2가지 제약조건을 고려한 인접 가능한 경우의 수는 다음과 같다.

 

$$ C1 \to C2, C3$$

$$ C2 \to C1, C3, C4$$

$$ C3 \to C1, C2$$

$$ C4 \to C2$$

 

최대 비용을 저장할 2차원 배열을 DP라 하자. DP는 4 by n( n은 최대열 )이라 할 때, 만약 $j$번째 열이 Case i로 놓일때의 최대 합은 DP[i][j]를 의미한다. 그리고 DP[i][j]는 i에 따라서 고려해야 될 Case가 달라진다. 

 

따라서 각 열에 따라 Case에 따른 돌이 놓인 곳의 합을 Value라는 배열에 저장하자.

 

 

Value 배열은 위와 같이 나오는데, 결국 해당 열에 놓을 조약돌이 특정한 Case일 때, 얻을 수 있는 값을 의미한다. 따라서 우리는 j열에 Case i와 같이 조약돌을 위치시켰을 때, 1~j열 까지 조약돌의 위치에 따라 얻을 수 있는 최대 값을 구하면 된다.

이때, 고려해야 될 것은 j열에 놓여지는 조약돌의 Case에 따라 j-1열에 올 수 있는 조약돌의 위치가 결정된다는 것이다. 예를 들어 j열에 Case 3의 조약돌이 위치했다고 하자. 그렇다면, j-1열에는 Case 1 혹은 Case 2 두 경우 밖에 오지 못한다. 따라서 2경우 중 큰 값과 j열에 Case 3에 해당되는 조약돌이 위치한 값을 더한 값이 최대가 되는 값이다. 

따라서 DP에는 j열에 놓여지는 조약돌이 Case i와 같을 때 1~j열까지 조약돌을 놓았을 때 얻어지는 최대값이 되는 것이다.
 
이를 구현해 보면 다음과 같다.

 

---

정답

#include<iostream>
#include<algorithm>

using namespace std;

int Value[4][100001];
int DP[4][100001];

int main()
{
	int i, j, cnt;

	cin >> cnt;

	// Input
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < cnt; j++)
		{
			cin >> Value[i][j];
		}
	}

	// 1,3번째 행이 동시에 조약돌이 놓일 때 Value
	for (i = 0; i < cnt; i++)
	{
		Value[3][i] = Value[0][i] + Value[2][i];
	}

	// Case 1. -> Case2,3
	// Case 2. -> Case1,3,4
	// Case 3. -> Case1,2
	// Case 4. -> Case2

	// i번째 열이 Case x일 때, 1~i열 까지의 최대합
	DP[0][0] = Value[0][0];
	DP[1][0] = Value[1][0];
	DP[2][0] = Value[2][0];
	DP[3][0] = Value[3][0];

	for (i = 1; i < cnt; i++)
	{
		DP[0][i] = max(DP[1][i - 1], DP[2][i - 1]) + Value[0][i];
		DP[1][i] = max(max(DP[0][i - 1], DP[2][i - 1]), DP[3][i - 1]) + Value[1][i];
		DP[2][i] = max(DP[0][i - 1], DP[1][i - 1]) + Value[2][i];
		DP[3][i] = DP[1][i - 1] + Value[3][i];
	}

	cout << max(max(max(DP[0][cnt - 1], DP[1][cnt - 1]), DP[2][cnt - 1]), DP[3][cnt - 1]) << endl;

	return 0;
}

아래 max value를 구하는 과정을 보면 각 Case에 따라서 조건문이 다른 것을 확인할 수 있다. 따라서 이렇게 구한 DP의 n번째 열의 최대값이 결국 해당 테이블에서 얻을 수 있는 최대값이 되는 것이다.

처음에는 앞에서 부터 접근하는 방법을 시도하였으나, 그렇게 진행하면 j-1번째 열에서 선택되는 Case에 따라 수많은 경우의 수가 발생되기 때문에 Dynamic Programming 방법으로 접근할 수 없음을 주의하자.