백준 2961 도영이가 만든 맛있는 음식

출처: https://www.acmicpc.net/problem/2961

분류: 재귀

---

접근방식

N이 1 ~ 10 으로 아주 작아서 백트래킹으로 모든 조합을 다 계산해서 풀 수 있었습니다.

처음에는 뭐에 홀렸는지 단순히 이중 포문으로 모든 경우를 다 체크할 수 있지 않나? 라고 생각했었네요...

단순히 이렇게 하면 중간을 건너뛴 1, 3 같은 조합은 체크할 수가 없겠죠 ㅠㅠ

s는 곱이고 b는 합이기 때문에 초기값으로 1, 0을 넣고 시작해줬습니다.

처음을 안 넣었을 경우는 계산하면 안 되기 때문에 각 케이스에서 재료를 넣어서 새롭게 만든 조합의 차만 생각을 해줬습니다.

 

해결방법

let n = Int(readLine()!)!
var flavors = [[Int]]()
for _ in 0..<n {
    flavors.append(readLine()!.split(separator: " ").map({ Int(String($0))! }))
}

var minDiff = Int.max

func combine(_ index: Int, s: Int, b: Int) {
    guard index < n else { return }
    let newS = s * flavors[index][0]
    let newB = b + flavors[index][1]
    if minDiff > abs(newS-newB) {
        minDiff = abs(newS-newB)
    }
    combine(index+1, s: newS, b: newB)
    combine(index+1, s: s, b: b)
}

combine(0, s: 1, b: 0)
print(minDiff)

 

배운점

정신 똑땍이 차리자.