랜선 자르기 ( 1654 번 )

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

 

---

🧠 알고리즘

• 이분 탐색 (Binary Search)

 

✔️ 동작 방식

[ 핵심 아이디어 ]

• 랜선을 어떤 길이로 자를지(now_len) 를 기준으로
  → 그 길이로 N개 이상 만들 수 있는지 판단한다.
• 가능한 길이 중 최댓값을 찾는 문제이므로
  → 조건을 만족하면 더 큰 길이 탐색,
  → 불만족하면 길이를 줄인다.

 

[ 로직 요약 ]

• 가능한 랜선 길이의 범위를 l = 1, r = max(n_list)로 설정
• now_len= (l + r) // 2 를 현재 자를 길이로 설정
• 모든 랜선에 대해 랜선 길이 // now_len로 만들 수 있는 개수 합산
• 개수가 n 이상이면 →  현재 길이는 가능 → answer 갱신 → 더 긴 길이 탐색 (l = mid + 1)
• 부족하면 → 길이를 줄임 (r = mid - 1)
• 탐색 종료 후 answer 출력

---

 

🧾 코드

import sys

def _main():
    l, r = 1, max(n_list)

    while l <= r:
        now_len = (l + r) // 2
        now_count = 0

        for n_value in n_list:
            now_count += (n_value // now_len)

        if now_count >= n:
            answer = now_len
            l = now_len + 1
        else:
            r = now_len - 1

    return answer
    

k, n = map(int, sys.stdin.readline().rstrip().split())
n_list = tuple(int(sys.stdin.readline().rstrip()) for _ in range(k))
print(_main())

---

 

⏱️ 시간 복잡도

while l <= r : 이분 탐색을 통한 최적의 길이 찾기 ( 로그 시간 )
    for n_value in n_list : 랜선을 순회하며 현재 갯수 구하기 ( 선형 시간 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )