[Medium] CubePacking
Topcoder SRM 507 Div1
큐브를 다 쌓고 박스로 포장했을 때, 박스안의 빈공간이 더 적게 남을 수록 전체 부피가 작아진다
박스안의 빈공간을 작게 만드는 것이 목표가 되었다.
빈공간의 부피가 k가 되도록 박스포장을 할 수 있냐? 라는 문제를 생각해보자
그 박스의 부피 V = (큐브의 부피합) + k 이고, 이 V를 V = a * b * c (a,b,c는 자연수) 로 나타낼 수 있냐? 라는 문제가 된다.
V의 약수들을 구한 뒤, 거기서 a, b를 고르는 경우를 모두 다 체크해보면 된다
k의 범위는 어떻게 될까?
L큐브를 일자로 쌓고 나머지 1큐브도 그 위에 L*L 로 쌓은 상황을 생각해보자
이 경우 생길 수 있는 빈공간의 개수는 0개~L*L-1개 이다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| bool isPossible(int vol, int Nb, int L) { | |
| vector<int> divs; | |
| for (int i = 1; i * i <= vol; ++i) { | |
| if (vol % i == 0) { | |
| divs.push_back(i); | |
| if (i * i < vol) { | |
| divs.push_back(vol / i); | |
| } | |
| } | |
| } | |
| sort(divs.begin(), divs.end()); | |
| for (int i = 0; i < divs.size(); ++i) { | |
| int a = divs[i]; | |
| if (vol < (long long)a * a * a) { | |
| break; | |
| } | |
| for (int j = i; j < divs.size(); ++j) { | |
| int b = divs[j]; | |
| if (vol < (long long)a * b * b) { | |
| break; | |
| } | |
| if (vol % (a * b) != 0) { | |
| continue; | |
| } | |
| int c = vol / (a * b); | |
| if ((a / L) * (b / L) * (c / L) >= Nb) { | |
| return true; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| class CubePacking { | |
| public: | |
| int getMinimumVolume(int Ns, int Nb, int L) { | |
| if (Ns % (L * L) == 0) { | |
| return L * L * L * Nb + Ns; | |
| } | |
| int ans = L * L * (L * Nb + (Ns + (L * L) - 1) / (L * L)); | |
| for (int empty = L * L - Ns % (L * L) - 1; empty >= 0; --empty) { | |
| int vol = L * L * L * Nb + Ns + empty; | |
| if (isPossible(vol, Nb, L)) { | |
| ans = vol; | |
| } | |
| } | |
| return ans; | |
| } | |
| }; |