출처: https://www.acmicpc.net/problem/1493
재휘는 length × width × height 크기의 박스를 가지고 있다. 그리고 재휘는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)
재휘가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.
입력 형식
첫째 줄에 세 자연수 length width height가 주어진다.
둘째 줄에 재휘가 가지고 있는 큐브의 종류의 개수 N이 주어진다.
셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 $2^i$에서 i이다.
출력 형식
첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.
제한 조건
예제 입력 1
4 4 8 3 0 10 1 10 2 1
예제 출력 1
9
예제 입력 2
4 4 8 3 0 10 1 10 2 10
예제 출력 2
2
예제 입력 3
10 10 11 1 0 2000
예제 출력 3
1100
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int l = sc.nextInt();
int w = sc.nextInt();
int h = sc.nextInt();
int n = sc.nextInt();
int[][] blocks = new int[n][2];
for (int i = 0; i < n; i++) {
blocks[i][0] = sc.nextInt(); // 블록 크기의 지수
blocks[i][1] = sc.nextInt(); // 블록 개수
}
System.out.println(fillBox(l, w, h, blocks));
}
public static int fillBox(int l, int w, int h, int[][] blocks) {
Arrays.sort(blocks, (a, b) -> b[0] - a[0]); // 블록 크기 순으로 정렬
long totalCount = 0;
long volume = (long) l w h; // 상자의 전체 부피
long usedVolume = 0;
for (int i = 0; i < blocks.length; i++) {
long size = ____; // 블록의 한 변 크기
int count = blocks[i][1];
if (volume <= usedVolume) {
break; // 상자를 이미 채웠다면 종료
}
long maxCount = ____; // 현재 크기로 채울 수 있는 최대 개수
maxCount -= usedVolume / (size size size); // 이미 채워진 공간 제외
long useCount = Math.min(count, maxCount);
usedVolume += useCount (size size * size);
totalCount += useCount;
}
// 상자를 다 채웠는지 확인
if (____) {
return (int) totalCount;
} else {
return -1;
}
}
}
빈칸 1: X
정답: (1 << blocks[i][0])
해설: blocks[i][0]은 블록 크기를 $2^k$ 형태로 나타낸 지수입니다. 따라서 블록 크기를 계산하려면 $2^k$를 구해야 합니다. 1 << blocks[i][0]은 비트 연산을 사용하여 $2^k$를 계산하는 효율적인 방법입니다.
-> 나는 blocks[i][0]라고 골랐다.만약 blocks[i][0]를 그대로 사용한다면, 그것은 단순히 지수 값일 뿐이며, 블록의 실제 사이즈를 나타내지 않는다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 $2^i$에서 i이다. 이 조건을 못봄
빈칸 2: O
정답: (l / size) (w / size) (h / size)
해설: 최대 블록 개수는 상자의 각 차원에서 해당 블록 크기로 몇 개가 들어갈 수 있는지를 계산한 값의 곱으로 구합니다.
빈칸 3: O
정답: usedVolume == volume
해설: volume은 상자의 전체 부피, usedVolume은 사용된 블록의 총 부피입니다. 상자가 완전히 채워졌다면, usedVolume과 volume이 같아야 합니다.
