[백준] 1052: 물병 - Swift 풀이

노션에서 보기

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

 

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다.
그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

 

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

 

• 입력: 첫째 줄에 N과 K가 주어진다. N은 10^7보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.
• 출력: 첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

---

문제 해설

하..이 문제는 정말 문제 이해가 한참 걸렸다.

K개를 넘지 않는 비어 있지 않은 물병이라는 말이 너무 어렵고 봐도 봐도 번역기 잘못 돌린 문장 같이 보인다.

 

어찌저찌 이해한 바로는, 물이 1리터 씩 들어 있는 N개의 물병을 K개 이하의 개수로 합쳐보라는 것이다.

물 합치기는 물병에 같은 양의 물이 들어있을 때만 가능하며,

현재 상태로 더 이상 합치기가 불가능하다면 상점에서 1리터가 들어 있는 물병을 무한대로 사올 수 있다.

K개 이하로 합쳐지기 까지 추가로 구매해야하는 물병의 수를 구하면 된다.

 

문제 이해를 마친 다음에 그래서 어떻게 구할 건지 생각해내는 것도 상당히 어려웠다.

우선 합칠 수 있는 조건은 2048 게임을 생각하면 됐다. 무조건 2의 제곱수여야만 합칠 수 있는 조건이 된다. 모든 물병은 1에서 시작하므로, 차례로 합친다고 했을 때 2의 제곱수만 나올 수밖에 없다.

 

만약 33개의 물병에서 시작한다고 했을 때, 합칠 수 있는 만큼 최대한 합치면 [32, 1]의 2개의 물병이 남는다.

K가 2보다 크다면 물병 추가 구매 없이 0이 답일 것이고, K가 1이라면 물병 31개(32-1)를 추가로 구매해서 [64]를 만들어야 한다.

 

또, 물병이 177개라면 최대로 합쳤을 때 [128, 32, 16, 1]이 된다. K가 3이라면 15개(16-1)를 추가로 구매, K가 1이라면 79개(128 - (32 + 16 + 1))개를 구매하면 된다.

---

풀이

N에서 나올 수 있는 가장 큰 2의 제곱수로 배열을 구성하기 위해 먼저 2의 제곱수 배열을 만들어 주었다.

import Foundation

// 10^7이하의 2의 제곱수 배열
var t: Int32 = 1
var count: Float = 0
var twoPowArr = [Int32]()
let max: Float = pow(10, 7)

while t <= Int32(max) {
    t = Int32(pow(2.0, count))
    twoPowArr.append(t)
    count += 1
}
twoPowArr.reverse()

 

그리고 입력을 읽어온 뒤,

//입력 읽어오기
let inputArr = readLine()!.split(separator: " ").map{ Int32($0)! }
var n = inputArr[0]
let k = inputArr[1]

 

현재 물병으로 합칠 수 있는 만큼 합친 물병의 배열을 만들어 주었다.

만약 N이 2의 제곱수라면(1 포함) 배열 생성을 멈춰도 되므로 break 지점으로 삼고,

그렇지 않다면 twoPowArr에서 어느 위치에 있는 지 찾아서 최대의 2의 제곱수를 bottles 배열에 추가해주고, 그 값만큼 뺀 수를 다시 makeArr 의 인자로 전달하여 함수를 재귀적으로 실행하도록 했다.

//상점 구매 전 최대한 합친 물병 집단 만들기
var bottles = [Int32]()
makeArr(n)
bottles.sort(by: <)

func makeArr(_ n: Int32) {
    for i in 0..<twoPowArr.count {
        if n == twoPowArr[i] {
            bottles.append(n)
            break
        } else if n < twoPowArr[i],
                  n > twoPowArr[i+1] {
            bottles.append(twoPowArr[i+1])
            makeArr(n-twoPowArr[i+1])
        }
    }
}

 

위에서 구성한 물병의 수가 K보다 작거나 같다면 0을 출력하며 빠른 종료.

guard bottles.count > k else {
    print(0)
    exit(EXIT_SUCCESS)
}

 

아직 K보다 크다면 상점에서 물병을 새로 구매하는 addBottle을 실행하도록 했다.

카운트가 K보다 작거나 같아질 때까지,

bottles[0]과 bottles[1]이 같다면 전자에 2를 곱해서 합치고 ([2, 2, 16] → [4, 16] 같은 경우)

같지 않다면 물병을 두 수의 차만큼 구매한 뒤 합친 뒤 ([1, 8, 32] → [1 + 7, 8, 32] → [16, 32] 같은 경우)

합치는 과정이 끝나면 bottles[1]를 삭제하여 빈 물병을 처리(?)했다.

//새로 구매하기
var new: Int32 = 0
addBottle()
print(new)

func addBottle() {
    while bottles.count > k {
        if bottles[0] == bottles[1] {
            bottles[0] *= 2
        } else {
            new += bottles[1] - bottles[0]
            bottles[0] = bottles[1]*2
        }
        bottles.remove(at: 1)
    }
}

new를 출력하며 기나긴 여정 끝!

 

그런데 문제에서 말한 정답이 없는 경우는 아직도 찾아내지 못했다. 

물병 구매 수의 제약이 없는 이상 무조건 정답이 있을 수밖에 없는 것 같은데...

혹시나 이 글을 보고 계시고 정답이 없는 경우를 아신다면 꼭 좀 제보 부탁 드립니다 :)

---

맞았습니다!를 보고 나서 다른 분들의 풀이를 보니

맙소사 너무 짧고 간략했다.

 

2로 나눈 나머지와 몫을 활용하면 아주 짧게 쓸 수 있었다.

 

수학적 사고가 부족해서 그럴까?

나는 현실의 방법과 거의 일치하도록 코드를 구현하는 경향이 있는 것 같다...

 

다만, 나의 풀이는 시간이 12ms 밖에 걸리지 않은 반면

간략한 풀이들은 최소 232ms 이상이 걸려서 시간 차이는 꽤 됐다.

 

그럼...

끝!