랜선 자르기[백준 1654]

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

우선 문제를 보고 바로 이분 탐색의 접근 방법이 떠올랐다는 것은 스스로에게 칭찬해주고 싶다. 

최근에 이분 탐색 풀이에 크게 감명받고 한번쯤 이분 탐색을 꼭 곁들여 보는것 같다(혹시 이 접근은 아닐까 하는식??)

각설하고 

 

애를 먹었던 부분은 길이가 최대로 긴 부분까지 접근해야 하는데 이부분을 어떻게 할것이냐?? 

 

정답 코드 먼저!!

k, n = map(int, input().split())
l = []
for i in range(k) :
  l.append(int(input()))

l.sort()
result = 0
left = 1
right = l[len(l) - 1]

while left <= right :
  mid = (left + right) // 2
  
  total = 0
  for i in l :
    total += i // mid
  
  if total >= n :
    result = mid
    left = mid + 1
  elif total < n :
    right = mid - 1
    
print(result)

아래의 애를 먹었던 부분들에 대한 고민이 모두 해결된 코드다

1. 명확한 조건 설정 (left <= right)
2. 조건 내에서의 반복으로 값이 최댓값이 될때까지 다가간다. (이게 떠오르기가 너무 힘들었다.)

 

 

애를 먹었던 부분에 대한 코드이다.

while left <= right :
  mid = (left + right) // 2
  
  total = 0
  for i in l :
    total += i // mid
  
  if temp == n :
    result = mid
    break
  elif total >= n :
    left = mid + 1
  elif total < n :
    right = mid - 1
    
print(result)

위의 코드는 바로 탈출을 해버린다.

테스트 케이스가 맞았던 이유는 단지 운이였다. 

반례를 넣는순간 값은 틀린다. 조건을 달리 해주어야 겠다고 생각했다.

 

아래는 새로 등장한 방식

while True :
  mid = (left + right) // 2
  temp = 0
  for i in l :
    temp += i // mid
  
  if temp == n :
    result = mid
    temp = 0
    for i in l:
      temp += i // (mid + 1)

    if temp == n :
      left = mid + 1
      next
    else :
      break
  elif n > temp :
    right = mid
  elif n < temp :
    left = mid

경계값을 찾기위해 값이 달라지는 순간을 포착하려 했다. 

n값과 달라지는 순간이 길이가 최대로 길어지는 순간일 것이라 생각 위와 같이 코드를 작성했는데 시간 초과 였다.

 

 

시행 착오들

 

저기 런타임 에러는 left의 초기값을 0으로 설정해주어서 그렇다.(문제를 잘 읽자...)