백준 2163번: 초콜릿 자르기

[문제 링크]

2163번: 초콜릿 자르기

---

N X M 크기의 초콜릿을 가장 적게 자르는 횟수를 구하는 공식은 (N * M - 1)이다. 이 공식을 통해서도 쉽게 정답을 구할 수 있다.

 

필자는 dp를 연습하기 위해 공식을 사용하지 않고 점화식을 세워서 풀었다.

N X M 크기의 초콜릿을 가장 적게 자르는 횟수는 (y축을 1~N/2개 잘랐을 때 나오는 두개의 조각을 가장 적게 자르는 횟수 + 1)과 (x축을 1~M/2개 잘랐을 때 나오는 두개의 조각을 가장 적게 자르는 횟수 + 1) 중 최솟값이다.

따라서 점화식은 다음과 같이 나타낼 수 있다.

 

for(i = 1; i <= N/2; i++)

dp[N][M] = max(dp[N][M], dp(i, M) + dp(N-i, M) + 1)

for(j = 1; j <= M/2; j++)

dp[N][M] = max(dp[N][M], dp(N, i) + dp(N, M-i) + 1) 

 

N X M 과 M X N 초콜릿은 서로 모양만 다를뿐 같은 초콜릿이기 때문에 중복을 최소화하여 효율성을 높였다.

---

#include <iostream>
using namespace std;

const int INF = 987654321;
int memo[301][301];

inline int min(int a, int b) { return a < b ? a : b; }

int Topdown(int y, int x)
{
	if (y == 1 || x == 1) return y == 1 ? x - 1 : y - 1;

	int& retA = memo[y][x];
	int& retB = memo[x][y];

	if (retA != 0 || retB != 0) return retA;

	int ret = INF;

	for (int i = 1; i <= y / 2; i++) // 가로로 자르기
		ret = min(ret, Topdown(i, x) + Topdown(y - i, x) + 1);

	for (int i = 1; i <= x / 2; i++) // 세로로 자르기
		ret = min(ret, Topdown(y, i) + Topdown(y, x - i) + 1);

	return retA = retB = ret;
}

int main(void)
{
	int y, x;
	cin >> y >> x;

	// top-down
	cout << Topdown(y, x) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 71 day