[BOJ] 1493 박스 채우기

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이다.

4 4 8
3
0 10
1 10
2 1

출력

첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.

9

제한

• 1 ≤ length, width, height ≤ 106
• 1 ≤ n ≤ 20
• 0 ≤ Ai < 20
• 0 ≤ Bi ≤ 106
• Ai ≠ Aj (i ≠ j)

---

분할 정복 자신감 되찾기 프로젝트의 일환으로 푼 문제다. 그런데 오히려 더 깎아 먹은 것 같다. 다음엔 더 쉬운 문제를 풀어야겠다. 

 

분할 정복 유형에서 고른 문제지만 큐브를 가장 적게 사용해야 하기 때문에 오히려 그리디 쪽에 더 가깝지 않나 싶은 문제였다. 아니나 다를까 문제 유형에도 그리디가 있었다. 현재 가지고 있는 큐브 중에 가장 큰 걸 넣고 나머지 부분을 재귀 함수로 호출해준다. 이때 상자가 직육면체이기 때문에 예쁘게 떨어지지 않는다. 그래서 나머지를 세 부분으로 나눠서 함수를 3번을 호출해줘야 한다. 세 부분으로 나누어 주는게 문제의 핵심이었다고 생각한다. 

그리고 더 이상 남아있는 큐브를 넣을 수 없는 경우에 -1을 출력해준다.

 

 

후기)

손으로 써보지도 않고 머리만 데굴데굴 굴려서 풀려고 한 심보가 한 대 쥐어박고 싶다. 어제까지만 해도 문제 푸는 게 나름 재미있었는데 오늘은 왜 이렇게 재미가 없을까...