백준 1493번 박스 채우기 - SWIFT

문제

---

세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)

세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2^i에서 i이다.

 

출력

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

 

문제 링크

1493번: 박스 채우기

 

 

풀이

---

처음에는 조금 많이 헤맸다.

박스를 채웠다는 것을 어떻게 표현해야하는가 부터, 박스를 채우는 순서, 박스를 세워놓고 쌓아야하나, 박스를 눕혀놓고 쌓아햐하나 등등 여러가지를 고민했다.

그러다가 일단은 가장 큰 것부터 넣어보는게 맞겠구나 싶어서 큰 것부터 넣어보는데, 결국 위의 고민을 해결하지 못했다.

이 문제는 현재 내가 풀기엔 어렵다고 판단이 되어, 접근법을 찾아보았다.

 

접근법

일단 상자에 가장 큰 큐브부터 넣어보는 것이다.

만약 큐브가 상자에 들어가지 않는다면, 다음으로 큰 큐브를 넣어본다.

그런식으로 상자에 들어갈 수 있는 가장 큰 큐브를 찾아서 상자에 넣어보는 것이다.

이때, 큐브는 상자의 한 쪽 모서리에 딱 맞게 넣는다.

그렇게 되면 아래와 같이 박스를 큐브를 제외하고, 세 영역으로 나눌 수 있게 된다.▼

 

그렇게 되면 이 세 영역은 또 다른 크기의 상자가 되는 것이고, 계속해서 같은 방식으로 상자를 채울 수 있는 것이다.

큐브는 상자의 8개의 모서리 중 아무데나 선택해서 들어가면 되는 것이고, 좌표는 신경쓰지 않고 그저 큐브를 넣고 나온 나머지 영역의 크기에만 신경 쓰면 된다.

 

프로그램 동작

1. 큐브를 크기 순서대로 하나씩 상자에 대입해본다.
   만약 상자에 들어간다면, 위의 접근법 대로 세영역으로 나눠본다.
   큐브가 상자의 한쪽 면의 길이와 정확히 일치한 상태로 들어가면 세 영역이 나오지 않을 수도 있다.
   따라서 큐브를 넣음으로서 생긴 세 영역의 길이, 너비, 높이 중 하나라도 0이라면 더 이상 상자를 넣는 행위는 하지 않는다. (셋 중 하나라도 0이라면 공간이 없다는 뜻이다.)
2. 세 영역에 1번 과정을 반복해서 행한다.
3. 이때 모든 큐브를 대입했는데도 들어가는 큐브가 없는 상황이 발생하면, 이는 큐브로 상자를 꽉 채울 수 없는 상황이므로 -1을 출력한다.
4. 세 영역에 행한 1번 과정들이 모두 공간이 0이라서 들어갈 수 없는 상황이 된다면, 지금까지 넣은 큐브 개수를 출력한다.

 

Swift 코드

---

import Foundation

let lwh = readLine()!.split(separator: " ").map { Int(String($0))! }
let l = lwh[0], w = lwh[1], h = lwh[2]
let N = Int(readLine()!)!
var C = [(Int, Int)]()
var A = 0
var T = true

for _ in 0..<N {
    let AB = readLine()!.split(separator: " ").map { Int(String($0))! }
    C.append((Int(pow(2, Double(AB[0]))), AB[1]))
}
C.sort(by: { $0.0 > $1.0 })

func box(_ L: Int, _ W: Int, _ H: Int, _ I: Int) {
    if L == 0 || W == 0 || H == 0 {
        return
    }
    for i in I..<N {
        if L >= C[i].0 && W >= C[i].0 && H >= C[i].0 && C[i].1 > 0 {
            A += 1
            C[i].1 -= 1
            box(L - C[i].0, W, H, i)
            box(C[i].0, W - C[i].0, H, i)
            box(C[i].0, C[i].0, H - C[i].0, i)
            return
        }
    }
    T = false
}

box(l, w, h, 0)
if !T {
    print(-1)
} else {
    print(A)
}