1493 : 박스 채우기

풀이

! 큐브러버님 코드 참고했습니다 !

가장 큰 큐브부터 사용해서 박스를 채워야 하는 것은 증명할 것도 없이 자명하다.

부피로 으쌰으쌰 슥삭슥삭 멋있게 잘 계산해서 빈 공간을 잘 채워넣으면 된다.

사용했던 큐브를 보다 작은 단위로 쪼개나가자.

1*1*1 단위까지 쪼개지면, 그 큐브의 개수가 박스의 부피와 같은지를 비교해주자.

코드

#include <cstdio>
#include <algorithm>

typedef long long ll;

int l, w, h, n;
int a[22];
ll cnt, ans;

int main() {
	scanf("%d %d %d %d", &l, &w, &h, &n);
	for (int i = 0, x, y; i < n; i++) scanf("%d %d", &x, &y), a[x] = y;

	for (int i = 19; i >= 0; i--) {
		cnt <<= 3;
		ll tmp = std::min((ll)a[i], (ll)(l>>i)*(w>>i)*(h>>i)-cnt);
		cnt += tmp, ans += tmp;
	}

	printf("%lld", cnt == (ll)l * w * h ? ans : -1);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-03-19 11:12

Read more posts by this author