백준 2629 양팔저울

출처: www.acmicpc.net/problem/2629

분류: DP

---

접근방식

DFS 느낌으로 무게를 달 수 있는 경우들을 잘 세어야 하는 문제였습니다.

하나의 추를 놓고 3가지 경우를 생각해볼 수 있습니다.

1. 추를 추가하지 않았을 경우
2. 추를 구슬 반대쪽에 추가 ( weight + 추 )
3. 추를 구슬 쪽에 추가 ( |weight - 추| )

문제는 기저사례를 체크하는 부분이었는데,

단순히 무게만으로 확인했는지 체크하면 안 됩니다. 추를 몇 개를 사용했는지에 따라서 다음 무게들이 달라질 수 있기 때문에
몇 개의 추를 사용해 만든 무게인지 구분해줘야 합니다.

따라서 [현재 추][무게] 인 2차원 배열로 체크해줬네요!

추를 추가하지 않는 경우도 생각해줬기 때문에 마지막에 체크해줄 때는 추를 모두 사용했을 때의 배열 중에서 있는지만 확인해주면 됩니다 :)

마지막으로 추의 무게는 500g 에 최대 30개이기 때문에 무게를 확인할 수 있는 구슬은 최대 15000 까지 입니다. 따라서 15000이 넘는 구슬은 "N" 으로 처리해줍니다.

해결방법

let n = Int(readLine()!)!
var scales = readLine()!.split(separator: " ").map { Int(String($0))! }
let k = Int(readLine()!)!
var marbles = readLine()!.split(separator: " ").map { Int(String($0))! }
var check = [[Bool]](repeating: [Bool](repeating: false, count: 15005), count: scales.count+1)

func addScale(_ idx: Int, _ weight: Int) {
    
    guard !check[idx][weight] else { return }
    check[idx][weight] = true
    
    guard idx < scales.count else { return }
        
    addScale(idx+1, weight + scales[idx])
    addScale(idx+1, weight)
    addScale(idx+1, abs(weight - scales[idx]))
}

addScale(0, 0)
print(marbles.map({ ($0 > 1500 || !check[scales.count][$0]) ? "N" : "Y" }).joined(separator: " "))

 

배운점

같은 무게여도 추의 개수에 따라서 달라질 수 있다는 점을 생각하지 못했다... 어려웠다..

후 check 배열을 15000으로 해야되는데 1500으로 해서 무지하게 틀려댔다... 하 도랐..... ☠️