[ SWEA / 9282 ] 초콜릿과 건포도 (C++)

SW Expert Academy

 

난이도 : D4 
알고리즘 유형 : DP, 누적합 
풀이 시간 : 1시간 44분 

문제 풀이 

현수는 동현이에게 초콜릿 한 조각을 작은 두 조각으로 자를 때마다, 초기 큰 초콜릿에 있었던 건포도의 개수만큼의 수입을 받아야 한다. 동현이가 현수에게 지불해야 하는 건포도의 최소 양을 구하여라. 

 

문제를 이해하기 위해 두번째 TC를 예시로 들어보면, 초기 상태에서 다음과 같은 방법으로 자를 수 있다.

여기서 현수가 얻을 수 있는 수입은 나누기 이전의 건포도 개수만큼 받게 되고, 이런 방식으로 모든 초콜릿이 1 x 1 사이즈가 될 때까지 나누어야 한다. 

 

해당 문제에 접근하기 위해서는 구간 내의 건포도 총합을 먼저 구해야 한다. 왜냐하면 각 구간을 나눌 때마다 건포도 개수의 총합을 구하게 된다면 시간초과가 날 것이기 때문이다. 이는 2차원 배열의 누적합 방법을 사용하여 구할 수 있다. 

 

또한, 본 문제에서는 특정 구간의 누적합을 구할 줄도 알아야 한다. 

예를 들어, 3 x 3 초콜릿에서 (2, 2) ~ (3, 3) 구간에 해당하는 초콜릿의 면적을 구하고 싶을 때, 2차원 누적합 테이블에서 이 값을 확인하게 된다면 틀린 결과를 보일 것이다. 

실제 값은 21인데, 누적합에서 (3, 3)의 값은 39이다.

따라서, 이를 구해주기 위해서는 구간에 해당되지 않는 구간을 빼주고, 중복 뺄셈 되어지는 구간을 한 번 더해주면 해결할 수 있다.

중복되는 구간(노랑색 구간)을 더해주면 된다.

위 표에서 확인해보면, (2, 2) ~ (3, 3) 구간의 합을 구하기 위해서는 `grid[3][3] - grid[2 - 1][3] - grid[3][2 - 1] + grid[2 - 1][2 - 1]`을 진행해주면 21이라는 값을 구할 수 있다. 이를 시작 좌표를 (sr, sc)라고 하고, 종료 좌표를 (er, ec)라고 하여 수식으로 다시 작성해본다면,

`int sum = grid[er][ec] - grid[sr - 1][ec] - grid[er][sc - 1] + grid[sr - 1][sc - 1]` 이 된다.

 

이후 나눈 구간합에 대해 메모이제이션을 진행해주면 된다. dp 테이블은 4차원으로 구성이 되는데, 이는 시작 좌표 x, y와 종료 좌표 x, y 내의 건포도 총합에 대한 정보를 담고 있다. `dp[시작 row][시작 col][종료 row][종료 col]`

 

이후, 가로로 한 번, 세로로 한 번 각각 초콜릿을 잘라본 다음, 얻게 되는 건포도의 최솟값을 현재 자르기 전인 dp에 저장한다. 

// 가로로 자르기
for (int i = sr; i < er; i++) {
    dp[sr][sc][er][ec] = min(dp[sr][sc][er][ec], recur(sr, sc, i, ec) + recur(i + 1, sc, er, ec) + duplicate_sum);
}
// 세로로 자르기
for (int i = sc; i < ec; i++) {
    dp[sr][sc][er][ec] = min(dp[sr][sc][er][ec], recur(sr, sc, er, i) + recur(sr, i + 1, er, ec) + duplicate_sum);
}

위 코드에서 두 구간에 대해서 재귀를 들어가게 되고, `duplicate_sum` 변수의 경우에는 이전에 설명했던 특정 구간에 대한 구간합 정보이다. 이를 통해 초콜릿의 구간을 나누어 간 값을 누적하여 끌고 올라올 수 있다.

 

시간복잡도의 경우, DP 배열의 크기 만큼 탐색을 진행해주고, 재귀함수를 호출하는데 경우의 수만큼 진행되기 때문에, $O(n^2 * m^2 * (n + m))$ 만큼 소요된다.

 

코드

/*
n x m 크기의 건포도 초콜릿
하나의 건포도는 한 격자에만 속하고, 튀어나오지 않음

- 현수는 직사각형 전체를 일직선으로 자르는 행동만 가능함 -> 보상 요구
돈 대신 건포도를 지불
초콜릿 한 조각을 작은 두 조각으로 자를 떄마다, 초기 큰 초콜릿에 있었던 건포도의 개수만큼 받는다.
지불해야하는 건포도의 최소 양을 구하여라

풀이 : 
1. 일단 완전탐색 + 재귀함수로 접근하자.
	-> 시간초과난다.
2. 메모이제이션 사용한 DP로 풀이
	-> DP 테이블은 4차원으로 가져가기 : dp[a][b][c][d] ==> a : 시작 r, b : 시작 c, c : 종료 r, d : 종료 c
+ 중복 구간 계산을 방지하기 위해 누적합으로 건포도 개수를 구해놓자

*/

#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 2e9

using namespace std;

int t, n, m;
int dp[51][51][51][51];
int chocolate[51][51];
int prefix_sum[51][51];

void calcSum() {
	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < m + 1; j++)
			prefix_sum[i][j] = chocolate[i][j] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1];
	}
}


int recur(int sr, int sc, int er, int ec) {
	// 종료 조건
	if (sr == er && sc == ec)
		return 0;
	// 메모이제이션 조건
	if (dp[sr][sc][er][ec] != -1)
		return dp[sr][sc][er][ec];

	// duplicate_sum은 초콜릿의 범위를 나누기 이전에 해당하는 영역이기 때문에, 자르기 이전에 추가적으로 더해주어야 한다.
	// ex) 영역이 (1, 1), (1, 3)이고, 이 영역에서 구간을 나누고자 한다면, duplciated_sum은 해당 영역에 대한 초콜릿 값이다.
	int duplicate_sum = prefix_sum[er][ec] - prefix_sum[sr - 1][ec] - prefix_sum[er][sc - 1] + prefix_sum[sr - 1][sc - 1];
	dp[sr][sc][er][ec] = INF;
	
	// 가로로 자르기
	for (int i = sr; i < er; i++) {
		dp[sr][sc][er][ec] = min(dp[sr][sc][er][ec], recur(sr, sc, i, ec) + recur(i + 1, sc, er, ec) + duplicate_sum);
	}
	// 세로로 자르기
	for (int i = sc; i < ec; i++) {
		dp[sr][sc][er][ec] = min(dp[sr][sc][er][ec], recur(sr, sc, er, i) + recur(sr, i + 1, er, ec) + duplicate_sum);
	}

	return dp[sr][sc][er][ec];
}


int main() {
	cin >> t;
	for (int tc = 1; tc < t + 1; tc++) {
		cin >> n >> m;
		memset(prefix_sum, 0, sizeof(prefix_sum));
		memset(dp, -1, sizeof(dp));
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < m + 1; j++)
				cin >> chocolate[i][j];
		}
		// 누적합 진행
		calcSum();

		// dp 시작
		int ans = recur(1, 1, n, m);

		cout << '#' << tc << ' ' << ans << '\n';

	}
	return 0;
}

배운 점 

문제에 접근할 때, 습관적으로 손으로 문제를 풀며 규칙을 찾고있었다.

하지만, 풀리지 않았고 질문 게시판을 통해 문제의 힌트를 얻어 해결할 수 있었다. 생각해보면 이전에 들었던 강의인 완전탐색적으로 먼저 들어가서 생각해보자 라는 말이 떠올랐다. 본 문제도 완전탐색 -> 재귀 -> 메모이제이션 dp까지 생각이 가능한 문제이기 때문에, 문제접근법에 대해서 항상 생각하고 있어야 할 것이다.

+ 본 문제는 이전 정보가 다음 문제 해결에 영향을 주고 있지 않기 때문에 DP로 접근이 가능한 문제이다.