[Swift] BOJ 2805 나무 자르기

BOJ 2805 나무 자르기

 

✅ 나무 자르기

나동빈 책에서 같은 논리로 푸는걸 보았는데, 쉽다고 생각했는데 안되었음.

 

내가 이 문제를 못 푼 이유가 있는데, 이게 나무가 정확히 m만큼 나온다고 생각했었음.이게 경우에 따라서는 m보다 더 가져갈 수 밖에 없을 수도 있음

 

[틀린 코드 부분에서의 반례]

4 8

20 15 10 17

15일 때 -> result 7

14일 때 -> result 10

 

따라서 답은 14이지만 8보다는 많이 가져가면서 최소로 가져감.

 

이 로직이 가장 중요한 부분이었다.

 

 

 

✅ 코드

		// 나무의 수 N, 상근이가 가져가려는 나무의 길이 M
        let input = readLine()!.split(separator: " ").compactMap{ Int(String($0))}
        let m = input[1]
        let trees = readLine()!.split(separator: " ").compactMap{ Int(String($0)) }
        
        var min = 0
        var max = trees.max()! // Int자료형
        var mid = 0
        var result = 0
        var temp = 0
        
        while min < max {
            mid = (min + max) / 2
            // tree의 원소가 mid보다 크면 그 차이를 더해서 temp에 넣기
            temp = trees.map { $0 > mid ? $0 - mid : 0 }.reduce(0, +)
            
            if temp < m { // 너무 적게 가져간다면, 더 많이 가져가야 하므로
                max = mid // max를 미드로 바꾼다. 즉, mid값을 작게 만들어서 더 많이 가져가게끔
            } else {
                result = mid
                min = mid + 1
            }
        }
        
        print(result)

 

 

🟠 틀린 코드

        // 나무의 수 N, 상근이가 가져가려는 나무의 길이 M
        let input = readLine()!.split(separator: " ").compactMap{ Int(String($0))}
        let m = input[1]
        let trees = readLine()!.split(separator: " ").compactMap{ Int(String($0)) }
        
        var min = 0
        var max = trees.max()! // Int자료형
        var mid = 0
        var result = 0
        var temp = 0
        
        while min < max {
            mid = (min + max) / 2
            // tree의 원소가 mid보다 크면 그 차이를 더해서 temp에 넣기
            temp = trees.map { $0 > mid ? $0 - mid : 0 }.reduce(0, +)
            
            if temp == m {
                print(mid)
                break
            } else if temp < m { // 너무 적게 가져간다면, 더 많이 가져가야 하므로
                max = mid // max를 미드로 바꾼다. 즉, mid값을 작게 만들어서 더 많이 가져가게끔
            } else {
                min = mid + 1
            }
        }