[백준] 1654번 랜선 자르기

랜선을 왜 자르니 얘들아..

 

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

난 아직... 이분탐색의 while 탈출 조건을 아직 잘 못 잡는다.................ㅠㅠ 언제쯤 익숙해질까.. 어쨌든

 

맨 처음에 했던 생각은 최종 답안이랑 거의 비슷한데 반복 조건을 못잡고 헤맸다.

스터디에서 다같이 얘기하다가 집에서 풀어보기로하고 집에왔는데 가물가물,,ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

암튼 두번째 생각은 그래서 0부터 가장 짧은랜선까지를 범위로 생각했다.

 

그림과 같은 이유로 가장 작은걸 기준으로 자르면.. 될거라고 생각했다. 실제로 입력예제는 저렇게 풀어도 동작함.

 

 

근데!!!!!!!!!!!!!!!!!!!!! 이렇게 min이 극단적으로 짧은 경우는 얘기가 다르다...

N=4이므로 4개의 길이가 똑같은 랜선을 만들고싶은데, 상단처럼 가장 짧은것에 맞춘 것 보다

밑에 그림처럼 다른 선에 기준을 맞추고, 그걸 두번 자른게 더 긴 것을 알 수 있다.

자른 갯수가 6개가 돼도 상관 없다. 문제에 그렇게 써있으니까..

암튼 범위를 바꿔야 한다...ㅠㅠ 이걸 모르고 왜틀렸지 왜틀렸지 하면서 이상한데 계속 고치고있었음

범위는 랜선 길이의 max 이상으로는 길어질 수 없으므로, max를 기준으로 잡아서 자르기 시작함.

 

  # 1654번 : 랜선자르기
def binary_search_1654():
  k, n = map(int, input().split())
  lan_wires = []
  for _ in range(k):
    lan_wires.append(int(input()))

  # k, n = 4, 11
  # lan_wires = [802, 743, 457, 539]

  longest = max(lan_wires)

  left = 1
  right = longest
  result = 0

  while left <= right :
    center = (left + right) // 2
    # print('center=====', center)
    hap = 0

    for cm in lan_wires:
      hap += cm // center #쪼갠 랜선의 갯수의 합
    
    if hap < n:
      right = center -1 #길이를 작게만들어서 갯수가 늘어나게
    elif hap >= n :
      if center > result :
        result = center 
      left = center +1 #길이를 키워서 갯수가 줄어들게

  print(result)