[BOJ 10805 // C++] L 모양의 종이 자르기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10805번 문제인 L 모양의 종이 자르기이다.
문제는 아래 링크를 확인하자.

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

10805번: L 모양의 종이 자르기

L모양의 종이는 주어진 조건대로 자르면 (1) 직사각형 모양의 종이와 L모양의 종이 둘로 나뉘거나 (2) 직사각형 모양의 종이 둘로 나뉘게 된다.

 

h1,w1,h2,w2로 나타나는 L모양의 종이를 가장 적은 조각으로 나누는 경우의 수를 위와 같은 자르는 방법들의 최솟값으로 계산해 문제를 해결하자. 이 때 종이를 자르는 방법은 두 방향이 있으므로 둘을 모두 구현해야 함에 유의하자.

 

h1>h2, w1>w2 등의 조건이 있으므로 가능한 L모양의 종이의 가짓수가 충분히 적다는 점을 관찰하자. 여기에 대칭성을 이용해 h1<=w1을 만족하는 경우의 값만을 계산하는 등의 커팅을 하면 연산량을 대략 반토막낼 수 있으므로 위와 같은 방법으로도 문제를 충분히 해결할 수 있다..

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int H1, W1, H2, W2;
int dp1[51][51][51][51];
int dp2[51][51];

int func2(int h, int w) {
	int& ret = dp2[h][w];
	if (ret) return ret;
	if (h > w) return ret = func2(w, h);

	ret = 1000000007;
	for (int hh = 1; hh < h; hh++) ret = min(ret, func2(hh, w) + func2(h - hh, w));
	for (int ww = 1; ww < w; ww++) ret = min(ret, func2(h, ww) + func2(h, w - ww));

	return ret;
}

int func1(int h1, int w1, int h2, int w2) {
	int& ret = dp1[h1][w1][h2][w2];
	if (ret) return ret;
	if (h1 > w1) return ret = func1(w1, h1, w2, h2);

	ret = 1000000007;
	for (int h = 1; h < h2; h++) {
		ret = min(ret, func1(h1 - h, w1, h2 - h, w2) + func2(h, w1 - w2));
	}
	ret = min(ret, func2(h2, w1 - w2) + func2(h1 - h2, w1));
	for (int h = h2 + 1; h < h1; h++) {
		ret = min(ret, func2(h1 - h, w1) + func1(h, w1, h2, w2));
	}
	for (int w = 1; w < w2; w++) {
		ret = min(ret, func1(h1, w1 - w, h2, w2 - w) + func2(h1 - h2, w));
	}

	ret = min(ret, func2(h1 - h2, w2) + func2(h1, w1 - w2));
	for (int w = w2 + 1; w < w1; w++) {
		ret = min(ret, func2(h1, w1 - w) + func1(h1, w, h2, w2));
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 1; i < 51; i++) dp2[i][i] = 1;

	cin >> H1 >> W1 >> H2 >> W2;
	cout << func1(H1, W1, H2, W2);
}