티스토리 뷰

PS/백준

[백준/C++] 1493번 - 박스 채우기

unside 2021. 3. 17. 22:22

오늘의 문제!

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

입력

첫째 줄에 length width height 주어짐
둘째 줄에 N이 주어짐
셋째 줄부터 N개의 줄에 Ai와 Bi가 주어짐

풀이

박스에 들어가는 가장 큰 경우의 큐브부터 해결을 하여 최종적으로 1x1x1의 큐브로 줄여가면서 해결한다.
최초의 박스를 L x W x H 로 한다면 이때 들어갈 수 있는 큐브의 수는 각 L W H 를 큐브의 길이로 나눈 수로 구할 수 있다.

예를 들어 4 4 8 박스에 4 4 4 큐브를 넣는 수는 4/4 * 4/4 * 8/4 로 2개이다.
그리고 4 4 8 박스에 2 2 2 큐브를 넣는 수는 4/2 * 4/2 * 8/2 로 16개 이다.

이때 4 4 4 큐브를 최대로 넣고 2 2 2 큐브로 넣는 방법은 4 4 4 큐브는 2 2 2로 나누어 보면 4/2 * 4/2 * 4/2 로 8개의 2 2 2 큐브가 4 4 4 큐브를 이루는 것을 알 수 있다. 즉 4 4 8 박스를 4 4 4 큐브와 2 2 2 큐브로 채우면 4 4 4 큐브 2개를 쓰면된다.
단, 문제에서 주어진 것 처럼 4 4 4 큐브를 1개만 쓸 수 있으면 1개를 쓴다고 하고 넘어가서 2 2 2 큐브로 채웠을 때의 큐브 수에서 4 4 4 하나를 만들 때 들어가는 2 2 2 큐브 수를 빼주면 된다.

다른 예시로 2 3 3 을 예로 들어보면
2 3 3 박스를 2 2 2 큐브로 채우면 2/2 * 3/2 * 3/2 = 1개가 들어간다
그다음 1 1 1 큐브로 채우면 2/1 * 3/1 * 3/1 = 18개가 들어가는데

이때 2 2 2 큐브는 1 1 1 큐브 2/1 * 2/1 * 2/1 = 8개로 구성되므로
2 3 3을 1 1 1로 채운 것중 8개는 2 2 2 큐브 1개로 구성됨을 알 수 있다.

따라서 총 큐브의 수는 2 2 2 큐브 1개 1 1 1 큐브 10개로 구성된다.

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
 
struct inpType {
    int Ai;
    int Bi;
};
 
inpType inpArr[21];
long long empArr[21];
 
bool cmp (inpType a, inpType b){
    return a.Ai > b.Ai;
}
 
int main(void){
    long long L, W, H; //박스 크기
    cin >> L >> W >> H;
    int N;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> inpArr[i].Ai >> inpArr[i].Bi;
    }
    sort(inpArr,inpArr+N,cmp); //큰 큐브가 먼저 오게 정렬
    for(int i=0;i<N;i++){
        long long refValue = pow(2, inpArr[i].Ai); // 확인할 큐브의 길이
        long long l = L / refValue;
        long long w = W / refValue;
        long long h = H / refValue;
        long long emp = l * w * h; //확인할 큐브가 들어가는 개수
        for(int l=0;l<i;l++){ //기존에 넣었던 큐브를 현재 큐브로 치환 후 계산
            long long num = pow(2,inpArr[l].Ai) / refValue;
            num = pow(num,3);
            emp = emp - num * empArr[l]; //이전에 사용한 큐브의 구역에 들어가므로 해당 크기 만큼 빼줌
        }
        if(emp <= inpArr[i].Bi){ //최대치보다 작거나 같음 - 해당 개수 만큼 사용
            empArr[i] = emp;
        }
        else{ //최대치보다 많이 필요 - 최대치 만큼 사용
            empArr[i] = inpArr[i].Bi;
        }
    }
    long long compare = L * W * H;
    long long result = 0;
    long long sum = 0;
    for(int i=0;i<N;i++){
        sum = sum + pow(pow(2,inpArr[i].Ai),3) * empArr[i];
        result = result + empArr[i];
    }
    if(compare != sum){
        cout << -1;
    }
    else{
        cout << result;
    }
    return 0;
}
 
cs

생각정리...?

처음 풀때는 단순히 생각해서 풀려고해서 단순 나누기로 들어갔다 바로 실패를 맛보았다...

다음 방식으로는 박스에 x x x 큐브를 넣으면 박스는 총 8개로 나뉘어지는 것을 확인해서 해당 부분으로 풀려고 했으나 함수의 실행이 한번당 8번 실행되어 나중에는 수없는 많이 진행되서 해당 풀이도 넘어갔다.

그리디는 해당풀이가 옳바른지 아닌지를 빠르게 판단하는게 제일 중요한 것 같다.

저작자표시 비영리 동일조건 (새창열림)

'PS > 백준' 카테고리의 다른 글

[백준/C++] 2104번 - 부분배열 고르기  (0) 2021.03.19
[백준/C++] 1629번 - 곱셈  (0) 2021.03.18
[백준/C++] 15748번 - Rest Stops  (0) 2021.03.12
[백준/C++]13904번 - 과제  (0) 2021.03.11
10989번 수 정렬하기 3  (0) 2019.06.27
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/09   »
일 월 화 수 목 금 토
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30
글 보관함