[백준] 1654 랜선자르기 - Upper Bound/Lower Bound

1.문제

 

2.접근

이 문제의 해결포인트는 필요한 랜선의 개수 K개보다 1개 더 많은 K+1을 만족시키는 가장 짧은 랜선의 길이에서 1을 빼는 것이다.

이걸 해결하는 알고리즘이 Upper Bound인데 찾고자 하는 값을 초과하는 값이 처음으로 나타나는 위치이다.

 

Upper Bound와 같이 나오는 개념이 Lower Bound인데 아래 사이트에서 굉장히 자세히 설명해준다.

 

이해한 내용을 간단히 정리해 보자면,

Lower Bound는 찾고자 하는 값 이상의 값이 처음 나오는 위치

Upper Bound는 찾고자 하는 값을 초과하는 값이 처음 나오는 위치이다.

 

2-1. Lower Bound/Upper Bound

아래와 같이 4가 중복되어 나타나는 arr이라는 배열이 있고, 4라는 값을 찾아야 한다면??

 

Lower bound는 4이상의 값이 처음 나타나는 위치이므로 Lower Bound 값은 2가 될 것이다.

Upper bound는 4를 초과하는 값이 처음 나타는 위치는 arr[5]=7 이므로 Upper Bound 값은 5가 된다.

 

위 코드에서 보이는 것처럼 Lower Bound와 Upper Bound구현은 정말 한 끗 차이이다.

찾고자 하는 mid값이 찾는 값 K 미만이냐 이하냐, 다시말해 < 또는 <= 로 나뉘기 때문이다.

 

1)Lower Bound의 경우 K 값이 처음 나타났을 때의 위치를 알면 되기 때문에 else 조건, 즉 arr[mid] >= K 일 때 end=mid로 바꿔줌으로써 k가 처음 나타나는 위치를 탐색할 수 있다.

 

Lower Bound 실행결과

 

직접 실행해보면 arr[mid]=4를 이미 찾았는데도 탐색을 계속 하는 것을 확인할 수 있다.

이렇게 계속 k값을 찾았을 때도 k값의 위치를 포함하여 계속 탐색함으로써 Lower Bound를 찾을 수 있게 된다.

(Lower Bound의 위치를 리턴하고 싶을 때는 end를 리턴해줘야 한다.)

 

 

2)Upper Bound는 K값을 초과하는 값이 처음 나타나는 위치를 찾아야한다.

때문에 그냥 이분탐색이라면 탐색을 멈추고 값을 리턴하면 되지만 K값을 초과하는 값을 찾기 위해 arr[mid] <= K 의 조건식을 써줘야 한다.

arr를 예로 들면, 만약 mid=2라면 k값을 찾아도 탐색을 멈추지 않고 start=3 으로 바꾸고 탐색을 계속 하여 k=4를 초과하는 첫번째 값, 즉 7을 찾게 된다.(실제로 이렇게 반복문을 돌지는 않는다.)

 

아래는 Upper Bound 실행결과이다.

 

Upper Bound 실행결과

 

3.문제해결

다시 문제로 돌아와서, 문제에서 요구하는 값은 랜선의 최대 길이이다.

내가 원하는 랜선의 개수인 N개를 만족시키는 최대 랜선의 길이를 구해야 한는 말인데,

 

Upper Bound를 이용하면 N개를 만족시키는 랜선의 길이를 초과하는 첫번째 값을 얻게 되므로 마지막에 -1을 해주면 된다.

 

아직도 왜  Upper Bound를 이용해야하는 문제인지 모르겠다고?

문제에 나와있는 예제를 생각해보면 Upper Bound 201에서 1을 빼주면 랜선 11개를 만들 수 있는 최대 길이인 200이 나온다.

4.코드

import Foundation

let input = readLine()!.split(separator: " ").map{ Int(String($0))!}
 
let K = input[0]; let N = input[1]
var lines:[Int] = []

for _ in 0..<K{
    lines.append(Int(readLine()!)!)
}


var start = 1
var end = lines.max()!/(K/lines.count)
var mid = 0

end += 1
while(start<end){
    var count = 0
    mid = (start+end)/2
    for line in lines {
        count += (line/mid)
    }
    
    if count<N{ 
        end = mid
    }
    else{
        start = mid+1
    }
}

print(end-1)

 

**참고사이트

https://st-lab.tistory.com/269?category=948182 

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

https://12bme.tistory.com/120

[알고리즘] Lower bound, Upper bound

 

**공부하면서 작성하는 글입니다.

잘못된 정보가 있을시 언제든지 알려주세요:)