[swift] 백준 - 1654번: 랜선 자르기

1654번: 랜선 자르기

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

나의 풀이

let KN = readLine()!.split(separator: " ").map { Int($0)! }
let arr = (0..<KN[0]).map { _ in Int(readLine()!)! }
var left = 1
var right = arr.max()!
while left <= right {
    var count = 0
    let mid = (left + right) / 2
    for i in arr { count += (i / mid) }
    if count < KN[1] { right = mid - 1 }
    else { left = mid + 1 }
}
print(right)

 

- 이진탐색을 사용해서 문제를 풀 수 있었습니다.

 

- 이진탐색은 정렬된 배열에서 탐색할 수 있으며

left, right, mid 변수를 만들어 구현할 수 있습니다.

변수 이름에서 알 수 있듯이

left는 배열의 시작값(인덱스)

right는 배열의 마지막값(인덱스)

mid는 배열의 중간값(인덱스)

가 됩니다.

 

- 해당 문제를 이진탐색으로 풀어보겠습니다.

저희는 N개로 나눠질 수 있는 최대길이의 값을 구하고 있습니다.

나누는 랜선의 길이는 최소 1cm부터

주어진 랜선의 길이중 제일 큰 값까지 들어갈 수가 있습니다.

 

- 예제를 예로 들면

[802,743,457,539]의 랜선이 있고

최대 길이의 랜선을 최소 11개 만들고 싶어 합니다.

 

- 최대로 자를 수 있는 길이는 배열의 max값인 802가 됩니다.

하지만 딱 802cm 길이만큼의 하나의 선밖에 얻질 못하겠죠.

그렇다면 넉넉잡아 1cm부터 802cm 안에는 저희가 원하는

11개가 나오는 최대길이가 있을 겁니다.

 

- min = 1

max = 802

mid = (min + max) / 2

값이 각각 들어가게 됩니다.

 

- 이진탐색의 핵심은 min값이 max값을 초과할 때

저희가 원하는 값의 위치를 찾을 수 있습니다.

따라서 while문은 min값이 max값을 초과할 때까지

계산을 반복하게 됩니다.

 

- while문 안에서는

arr배열 안에 있는 선을 하나하나 mid값만큼 잘라보는 겁니다.

그리고 옳게 잘라진 선의 개수만큼 count에 넣습니다.

 

- mid값이 작을수록 촘촘하게 자르게 되니 선의 개수는 많아지고

mid값이 높을수록 선의 개수는 적어집니다.

 

- 만약 원하는 개수만큼 선이 안 나왔다면

mid값을 작게 해야겠죠?

현재 802가 들어있을 max값에 (mid-1) 값을 넣어 줍니다.

그럼 다음 반복에서는

작아진 max값 영향을 받아 mid는 작아지게 됩니다.

 

- 반대로 원하는 개수보다 선이 더 나왔다면

mid값을 크게 하기 위해

min값에 (mid+1)을 넣어줍니다.

 

- 이런 식으로 반복을 계속해 주다 보면

min값이 max값을 초과하게 되는 순간이 오는데요.

while문은 종료되며

 

- 최종적으로 min(left): 201, max(right): 200이 들어가 있습니다.

둘은 선의 개수가 교차되는 지점에서 멈추게 됩니다.

left의 값인 201cm는 10개가 잘리고

right의 값인 200cm는 11개가 잘리는 최댓값이 됩니다.

 

- 저도 복습할 겸 문제를 풀어썼다 보니

보다 명확한 개념을 위해서는

이진탐색과 lower bound , upper bound를 검색해서 공부해 보시는 걸 추천합니다.

 

---