[Swift] 백준_물약 구매(24954)

문제

 

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

24954번: 물약 구매

 

 

풀이

 

스위프트로 푼 사람이 나밖에 없어 좋은 풀이인지는 잘 모르겠다.

 

모든 경우를 다 따져봐야 가장 싸게 살 수 있는 방법을 알 것 같았다.

 

우선, 입력을 받으면서 다른 물약을 할인시키는 물약의 인덱스를 discount에 넣고, 아닌 물약들은 noDiscount에 넣어주었다.

이때, 다른 물약을 할인시키는 정보도 info라는 변수에 인덱스별로 넣어주었다.

 

다음으로 dfs를 이용해 discount에 있는 값들의 순열을 구해준다. 예시의 경우 [0,2,3]이 할인 정보를 가지고 있으므로 discount에 담겨있을텐데 dfs를 거치고 나면 total이라는 변수에는 [[0,2,3],[0,3,2],[2,0,3],[2,3,0],[3,0,2],[3,2,0]]이 들어가있을 것이다.

이때, discount가 비어있다면 할인되는 물약이 없는 것이므로 그냥 price내의 값을 모두 더해서 출력해주면 된다.

 

[0,2,3]의 경우를 보자.

우선 0이 가장 처음이므로 tempPrice에는 할인이 되지 않은 가격이 있을 것이다. 이를 먼저 temp에 더해준다.

이때 info를 보면 0번째(1번째 물약)은 세번째와 네번째 물약을 할인시키므로 tempPrice[info[0] - 1]을 할인된 가격으로 바꿔준다. 만약 0이하라면 1로 바꿔준다.

 

이렇게 하고나면 다음에 2가 들어왔을때 tempPrice[2]의 가격은 할인된 가격이 되어있을 것이다. 마찬가지로 차례대로 가격을 할인시키며 순서대로 더해주면 결과를 구할 수 있다.

 

noDiscount에 있는 물약들은 다른 물약을 할인시키지 않으므로 굳이 먼저 살 이유가 없다. 그래서 각 반복문에서 마지막에 더해주었다.

import Foundation

let n = Int(readLine()!)!
let price = readLine()!.split(separator: " ").map { Int(String($0))! }
var result = 0
var info: [[[Int]]] = []
var discount: [Int] = []
var noDiscount: [Int] = []
var total: [[Int]] = []
var check = [Bool](repeating: false, count: n)
for i in 0..<n {
    let p = Int(readLine()!)!
    if p == 0 {
        info.append([])
        noDiscount.append(i)
        continue
    }
    discount.append(i)
    var temp: [[Int]] = []
    for _ in 0..<p {
        let input = readLine()!.split(separator: " ").map { Int(String($0))! }
        temp.append(input)
    }
    info.append(temp)
}
func dfs(_ arr: [Int]) {
    if arr.count == discount.count {
        total.append(arr)
    }
    for i in 0..<discount.count {
        if !check[i] {
            check[i] = true
            dfs(arr + [discount[i]])
            check[i] = false
        }
    }
}
if discount.isEmpty {
    print(price.reduce(0) { $0 + $1 })
    exit(0)
}
dfs([])
for arr in total {
    var temp = 0
    var tempPrice = price
    for i in 0..<arr.count {
        temp += tempPrice[arr[i]]
        for info in info[arr[i]] {
            let newPrice = tempPrice[info[0] - 1] - info[1]
            tempPrice[info[0] - 1] = newPrice <= 0 ? 1 : newPrice
        }
    }
    for item in noDiscount {
        temp += tempPrice[item]
    }
    result = result == 0 ? temp : min(temp,result)
}
print(result)

 

_____________________________________________________________________________________________________

 

생각난 방법이 있다면 우선 구현해보는 것도 나쁘지않을듯