BOJ(백준) 9029번 정육면체

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

9029번: 정육면체

특별할 것 없는 3차원 dp이다.

 

높이, 가로, 세로를 차원으로 하는 3차원 dp배열을 만들고 해당하는 높이, 가로, 세로를 가진 블럭을 최소 개수의 정육면체로 나눌 때 그 최소 개수를 배열에 저장하면 된다.

 

재귀를 통한 탑다운 방식으로 dp를 구현하면 깔끔하게 코드가 짜일 거 같아서 시도해봤는데 예상대로 잘 됐다. 높이, 세로, 가로가 같다면 1을 리턴하고 그 외에는 반복문을 돌면서 블럭을 두개로 나눌 수 있는 방법 전부에 대하여 나뉘어진 블럭 각각의 dp배열 값을 합친 것의 최소값을 구하고, 그 값을 배열에 저장함과 동시에 리턴하여 중복된 계산을 방지한다.

 

AC code

#include <bits/stdc++.h>
using namespace std;
int T,W,L,H,arr[201][201][201];

int func(int w,int l,int h) {
	if(arr[w][l][h]) return arr[w][l][h];
	if(w==l&&l==h) return 1;
	int mn=INT_MAX;
	for(int i=1;i<=w/2;i++) mn=min(mn,func(i,l,h)+func(w-i,l,h));
	for(int i=1;i<=l/2;i++) mn=min(mn,func(w,i,h)+func(w,l-i,h)); 
	for(int i=1;i<=h/2;i++) mn=min(mn,func(w,l,i)+func(w,l,h-i));
	return arr[w][l][h]=mn; 
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>W>>L>>H;
		cout<<func(W,L,H)<<"\n";
	}
}

 

처음에는 재귀 함수 내의 반복문을 0<i<w, l, h로 구간을 설정했는데 tle가 나와 중복되는 계산을 줄이도록 0<i<=w/2, l/2, h/2로 변경하니 AC가 나왔다.