1654번: 랜선 자르기 (python)

최소길이 1에서부터 최대길이 max(array)+1 사이에서 가장 적절한 길이를 찾으면 된다.

✅ 최대 길이가 max(array) 가 아닌 max(array)+1인 이유:

• 최대 길이를 max(array)로 설정하면

4 4
800
800
800
800

과 같이 k = n 이고 k 개의 숫자가 모두 같은 경우에는 800 이 최대 길이가 돼야 하는데 799 와 같이 근접할 뿐 800까지 도달하지 못하게 된다.

• 이진탐색법을 이용하기 위해서 최소길이와 최대길이 정중앙 값으로 진행하며, 만들 수 있는 총 랜선의 개수가 필요한 랜선의 개수보다
• 작을 경우 에는 시작 길이부터 중앙 길이 사이에서 반복, 클 경우 에는 중앙 길이에서부터 마지막 길이(최대 길이) 사이에서 반복한다.

for i in range(k):
        result += array[i] // center

result 변수에 각 랜선들을 center 값으로 나눈 값들을 더해 만들 수 있는 총 랜선의 개수를 구한다.

• start 길이가 end 길이보다 크거나 작아지는 경우 반복문 직전에 answer 에 담아둔 값을 출력한다.

참고사항

• 처음에 가능한 길이를 length 라는 리스트를 만들어 1부터 최댓값까지 넣어서 풀려고 했는데 (왜 이런 생각을 했는지 모르겠음)
  아무래도 최댓값이 2 <sup>31</sup> -1 이다보니 메모리초과 오류가 뜬다.

• 이진탐색법을 사용하지 않을 경우 시간초과 오류가 발생한다.