[백준/C++] 28420번: 카더가든

문제

https://www.acmicpc.net/problem/28420

---

문제 요약

너비가 a이고 길이가 b인 차와 너비가 a이고 길이가 c인 캠핑카가 있다.

 

차와 캠핑카는 3개의 그림 모양으로 n × m 크기의 화전역에 배치할 수 있다.

 

캠핑카와 차는 회전하거나 뒤집힐 수 없다.

 

화전역 땅의 단위 구역에는 흐림 정도가 주어진다.

 

차와 캠핑카가 차지하는 단위 구역의 흐림 정도 합의 최소를 출력한다.

---

코드

#include <iostream>

#define MAX 300

using namespace std;

int n, m, a, b, c;

int res = 1e9;

int ground[MAX + 1][MAX + 1];
int prefix[MAX + 1][MAX + 1];

// (x1, y1)부터 (x2, y2)까지의 누적합
int prefix_sum(int x1, int y1, int x2, int y2) {
	return prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1];
}

int main() {
	cin >> n >> m;
	cin >> a >> b >> c; // 너비, 차 길이, 캠핑카 길이

	// 입력
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ground[i][j];
		}
	}

	// ground 누적합 구하기
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			prefix[i][j] = ground[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
		}
	}

	// 첫 번째 탐색
	for (int i = 1; i <= n - a + 1; i++) {
		for (int j = 1; j <= m - b - c + 1; j++) {
			res = min(res, prefix_sum(i, j, i + a - 1, j + b + c - 1));
		}
	}

	// 두 번째 탐색
	for (int i = 1; i <= n - a - b + 1; i++) {
		for (int j = 1; j <= m - c - a + 1; j++) {
			res = min(res, prefix_sum(i, j, i + a - 1, j + c - 1) + prefix_sum(i + a, j + c, i + a + b - 1, j + a + c - 1));
		}
	}

	// 세 번째 탐색
	for (int i = 1; i <= n - a - c + 1; i++) {
		for (int j = 1; j <= m - b - a + 1; j++) {
			res = min(res, prefix_sum(i, j, i + a - 1, j + b - 1) + prefix_sum(i + a, j + b, i + a + c - 1, j + a + b - 1));
		}
	}

	cout << res;

}

---

코드 설명

1. 화전역 땅에 주어진 흐림 정도 정보를 2차원 배열 ground에 입력 받는다.

 

2. '(1, 1)부터 (i, j)까지 단위 구역의 흐림 정도 합' prefix[i][j]를 정의한다.

 

3. '(x1, y1)부터 (x2, y2)까지 단위 구역의 흐림 정도 합' prefix_sum(x1, y1, x2, y2)를 정의한다.

 

3. 모양 3개를 경우의 수로 나누어서 완전 탐색을 진행한다.

---

고찰

식이 복잡하지만, 해당 인덱스에 제대로 접근했는지 출력으로 확인해보면서 코드를 작성하면 쉽다.