[백준][C++] 5463: 건포도

문제 링크: https://www.acmicpc.net/problem/5463

 

IOI 2009 문제입니다. SWEA에 똑같은 문제가 있는데 풀이는 여기에 올려놨습니다.

SWEA에서는 맞았는데 백준에서는 틀렸다고 나와서 왜 그런지 몇시간동안 삽질을 하면서 원인을 찾아봤는데 원인은 배열 음수인덱스 접근때문이었습니다.

C++에서 배열 범위를 넘어가 접근하는 것은 Undefined Behavior이기 때문에 SWEA에서 운좋게(?) 통과가 됐었나봅니다. 이것때문에 몇 시간을 삽질했는지 후우;

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;


const int INF = INT_MAX;
const int MAX_LEN = 51;
const int MAX_VAL = 1000;

int cache[MAX_LEN][MAX_LEN][MAX_LEN][MAX_LEN];	// y, x, height, width
int chocolate[MAX_LEN][MAX_LEN];    // 초콜릿 한 칸당 위에 있는 건포도의 수
int c_sum[MAX_LEN][MAX_LEN];	// 누적합

inline int raisin_sum(int y, int x, int height, int width) {
	int y2 = y + height - 1,
		x2 = x + width - 1,
		y1 = y,
		x1 = x;

	int base = c_sum[y2][x2];
	if (y1 > 0) base -= c_sum[y1 - 1][x2];
	if (x1 > 0) base -= c_sum[y2][x1 - 1];
	if (y1 > 0 && x1 > 0) base += c_sum[y1 - 1][x1 - 1];

	return base;
}

inline int raisin_sum(int y, int x, int height, int width) {
	int y2 = y + height - 1,
		x2 = x + width - 1,
		y1 = y,
		x1 = x;

	return c_sum[y2][x2]
		- c_sum[y2][x1 - 1]
		- c_sum[y1 - 1][x2]
		+ c_sum[y1 - 1][x1 - 1];
}

int solve(int y, int x, int height, int width) {
	// base
	if (width == 1 && height == 1) return 0;

	int& ret = cache[y][x][height][width];
	if (ret != -1) return ret;
	ret = INF;


	const int base_raisins = raisin_sum(y, x, height, width);
	int best_payment = INF;

	// 가로로 자르기
	for (int cut_height = 1; cut_height < height; ++cut_height) {
		int payment = solve(y, x, cut_height, width) + solve(y + cut_height, x, height - cut_height, width);
		best_payment = min(best_payment, payment);
	}

	// 세로로 자르기
	for (int cut_width = 1; cut_width < width; ++cut_width) {
		int payment = solve(y, x, height, cut_width) + solve(y, x + cut_width, height, width - cut_width);
		best_payment = min(best_payment, payment);
	}

	return ret = best_payment + base_raisins;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);


	memset(cache, -1, sizeof(cache));

	int R, C;
	cin >> R >> C;

	assert(1 <= R && R <= MAX_LEN);
	assert(1 <= C && C <= MAX_LEN);

	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < C; ++j) {
			cin >> chocolate[i][j];
			assert(0 <= chocolate[i][j] && chocolate[i][j] <= MAX_VAL);
		}
	}


	// 누적합 구하기
	for (int i = 0; i < R; ++i)
		for (int j = 0; j < C; ++j)
			c_sum[i][j] = (j == 0 ? chocolate[i][j] : c_sum[i][j - 1] + chocolate[i][j]);

	for (int i = 1; i < R; ++i)
		for (int j = 0; j < C; ++j)
			c_sum[i][j] = c_sum[i - 1][j] + c_sum[i][j];

	cout << solve(0, 0, R, C) << '\n';


	return 0;
}

앞으로는 귀찮아도 vector를 써야겠습니다. 후 몇시간이나 삽질을 한건지..