[BOJ] 랜선 자르기

 

 

나의 코드 

 

a,b = map(int,input().split())
arr = [int(input()) for _ in range(a)]
k = 1
ans = []
while True:
  imp = []
  for num in arr:
    t = num // k
    imp.append(t)
    k += 1
  if sum(imp) == b:
    break

while True:
  ans = []
  k += 1
  for num in arr:
    ans.append(num//k)
    
  if ans != imp:
    break
print(k-1)

분석 > 시간초과 날 것을 알고 있었지만, 효율성을 제외하고 일단 문제를 풀어보기 위해서 풀어보았다. 당연히 결과는 시간초과. 

 

 

해설 코드 

 

a,b = map(int,input().split())
arr = [int(input()) for _ in range(a)]
# 이분탐색을 위한 처음 위치와 끝 위치 지정
start,end = 1,max(arr)

while start <= end:
  mid = (start+end)//2
  # 선의 개수 
  cnt = 0

  for i in arr:
    cnt += i//mid
    
  # 최종 랜선의 개수가 만들고자 하는 랜선의 개수보다 클 때 
  if cnt >= b:
    start = mid + 1
    
  # 최종 랜선의 개수가 만들고자 하는 랜선의 개수보다 작을 때 
  else:
    end = mid - 1
print(end)

분석 > 이번 문제를 통해 이분탐색이라는 개념을 새롭게 알게 되었다. 이분탐색이란 간단히 말하면, 자료를 둘로 나누어 탐색하는 것이다. 책을 예로 들면, 내가 찾고자 하는 페이지가 124쪽인데 내가 아무렇게나 펴본 책 페이지가 66쪽이라면 66쪽보다 뒤에 있는 아이들만 탐색해서 124쪽을 찾아내는 것이다. 이 문제 또한 처음에 start 값과 end 값을 각각 1과 max(arr)로 지정해둔 다음 이의 절반 값을 mid로 지정하고 배열 내 값을 mid로 나눈 값을 모두 더한 최종 랜선의 개수가 만들고자 하는 랜선의 개수보다 크면 mid를 더 크게 만들어야 하기 때문에 start값을 mid + 1로 바꾸고, 그 외에는 end값을 mid - 1로 바꾸어 mid 크기를 줄여 최종 랜선의 개수가 커지게 만들어 문제를 해결하였다. 이분 탐색의 계산 복잡도는 O(logn) 이다. 

 

 

 

1654번: 랜선 자르기