1654번: 랜선 자르기 (이진 탐색)

아직 문제풀이 경험이 적어서 이진탐색 문제를 풀 때마다 매번 부등호의 등호를 결정하는 것이 헷갈린다. 이진탐색 관련 문제 풀이 경험을 늘려 이 점을 극복해야겠다 (혹시 이진탐색을 할 때 부등호 등호와 출력값을 정하는 팁이 있다면 댓글로 공유 부탁드립니다.!)

---

1654번: 랜선 자르기

 1에서부터 최대랜선길이를 각각 start,end로 시작해서 각 wire의 길이를 mid로 나눈 값의 합을 cnt라고 하였다. 아래 그림에서 보라색 영역은 가능한 랜선의 길이이며 주황색은 가능하지 않은 랜선의 길이이다. 만들 수 있는 최대의 랜선 길이를 원하니 아래 그림에서 보라색 영역에서 가장 오른쪽을 만족하는 녀석을 이진탐색으로 찾아내면된다. 

 

이진탐색에서 찾으려는 값이 mid보다 작으면 end를 mid - 1해서 start하고 mid 사이에 있는 값을 찾으면 되고 반대로 크면 start를 mid + 1해서 mid하고 end사이의 값을 찾으면 된다. 

• 만약 cnt >= n 이라면 start = mid + 1
• cnt < n 이라면 end = mid - 1

위처럼 이진탐색을 진행했을 때 탐색하고자 하는 값이 alpha(보라색 영역의 끝)이면 start는 0~alpha+1이 가능하고 end는 alpha~max가 가능하다. 종결조건과 출력할 값을 결정하기 위해 어느정도 탐색이 이루어진 후 발생할 수 있는 경우를 땆져보면서 종결조건과 출력할 것(start,mid,end중 하나)를 결정해보자. 

---

case1.  start = alpha -1, end = alpha + 3인 경우에 

1) mid = alpha + 1, start = alpha -1, end = alpha

2) mid = alpha - 1, start = alpha, end = alpha

3) mid = alpha, start = alpha + 1, end = alpha

즉 start >= end 인 경우에 end를 출력하면 될 듯하다. 

 

case2. start = alpha-3, end = alpha + 1인 경우에

1) mid = alpha - 1, start = alpha, end = alpha + 1

2) mid = alpha, start = alpha + 1, end = alpha + 1

3) mid = alpha +1, start = alpha+1, end = alpha 

즉 start > end 인 경우에 end를 출력하면 될 듯하다. 

 

case3. start = alpha, end=alpha+3 인경우에 

1) mid = alpha+1, start = alpha, end = alpha

2) mid  = alpha, start = alpha + 1, end = alpha

즉 start > end인 경우에 end를 출력하면 될 듯하다. 

 

case4. start = alpha-3, end = alpha인 경우에 

1) mid = alpha-2, start = alpha-1, end = alpha

2) mid = alpha-1, start = alpha, end = alpha

3) mid = alpha, start = alpha +1, end = alpha

이 경우 마찬가가지로 start > end인 경우에 end를 출력하면 될 듯하다. 

---

따라서 아래와 같이 종결조건, 반환값을 정할 수 있었고 이에 따라 이분탐색을 구현했다. 

• 만약 cnt >= n 이라면 start = mid + 1
• cnt < n 이라면 end = mid - 1
• start > end인 경우 end를 반환한다.

k,n = map(int,input().split())
wires = []
for i in range(k):
    wires.append(int(input()))
start = 1
end = max(wires)
mid = (start + end)//2
while start <= end:
    mid = (start+end)//2
    cnt = 0
    for i in wires:
        cnt += i//mid
    if cnt >= n:
        start = mid + 1
    else:
        end = mid-1
print(end)

사실 작성하면서 든 생각인데 이분탐색을 진행하면서 start는 0~alpha+1이 될 수 있고 end는 alpha~가 될 수 있으므로 종료조건은 end = alpha, start = alpha+1인 start > end이고 이분 탐색의 결과로 end를 출력하는 것이 당연하다...