[수업]정육면체

Intro..

이 문제는 DP 관련 문제이다.

DP 관련해서 정리해둔 게시글이 있기 때문에 참고할 것.

문제

풀이

직육면체에서 최소로 절단해서 정육면체를 만든 경우는
최소로 절단한만큼 비례해서 정육면체도 최소로 생성될거임.
즉, 최소로 생성된 정육면체 개수를 구해가면 됨.

우선, a=b는 return 1

또한, 가로 세로를 항상 가로<=세로로 보고 품(세로가 더 커도 가로로 보면 됨) => 7x2x8이면 2x7x8로 배치후 품.

a를 k로 자르면 k와 a-k로 나뉨 k는 1<=k<=a/2 : 그 이상은 할 필요 없음. 중복이니까!!

최종 핵심 : min(c(kxb) + c((a-k)xb)) min(c(axk) + c(ax(b-k))) => c(a,b)

아래는 DP가 채워져 나가는 배열 모습(최소 생성된 정육면체 개수들..)

a,b 1 2 3 4

1 1 2 3 4…
2 1 3 2
3
4
=> 마지막 인덱스가 정답이 되는것