[python]1654_랜선 자르기

사용한 자료구조 및 개념 : 이분 탐색 (Binary Search)

 

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

가능한 최대 길이를 효율적으로 찾기 위해 이분 탐색(Binary Search) 을 사용하였습니다.

 

🤓 문제 풀이 단계

1️⃣ 입력 받기 및 초기 설정

• 랜선의 개수 k와 필요한 랜선의 수 n을 입력받습니다.
• 이어서 각 랜선의 길이를 입력 받아 cables 리스트에 저장합니다.
• 이분 탐색을 위한 시작점 start를 1로, 종료점 end를 주어진 랜선들 중 최대 길이로 초기화합니다.

2️⃣ 이분 탐색을 통한 최대 길이 탐색

• while start <= end: 반복문을 통해 이분 탐색을 수행합니다.
• 중간 길이 mid를 계산하고 이 길이로 자를 수 있는 랜선의 개수 cnt를 구합니다.
• 만약 cnt가 목표치 n 이상이면 해당 길이 mid는 조건을 만족하므로 정답(ans)을 갱신하고 더 긴 길이를 찾기 위해 start를 늘립니다.
• 그렇지 않으면 길이를 줄이기 위해 end를 감소시킵니다.

3️⃣ 최종 결과 출력

• 이분 탐색이 완료되면 ans에는 n개의 랜선을 만들 수 있는 최대 길이가 저장되어 있습니다.

---

✅ 세부 구현 포인트 및 이점

• 이분 탐색(Binary Search):
  • 이분 탐색을 사용함으로써 가능한 길이의 범위를 매번 절반으로 줄여가며 답을 찾습니다.
  • 이로 인해 전체 탐색 시간을 O(log M)으로 줄일 수 있어 랜선 길이의 최대값이 매우 클 때도 효율적으로 처리할 수 있습니다.
• 탐색 범위 설정:
  • start를 1로 end를 주어진 랜선들 중 최대 길이로 설정하여 초기 범위를 정합니다.
    (start값이 1인 이유는 랜선을 자를 수 있는 최소 값이 1이기 때문입니다.)
  • 가능한 랜선 길이의 최대 범위 내에서 조건을 만족하는 최대 값을 찾습니다.
• 최적화:
  • 각 단계에서 cnt를 계산하면서 현재 길이 mid로 충분한 랜선을 만들 수 있는지 확인합니다.
  • 이 과정을 통해 불필요한 길이 검사는 최소화하고 탐색 범위를 빠르게 줄여갑니다.

---

Solution Code

k, n = map(int, input().split())
cables = [int(input()) for _ in range(k)]

start, end = 1, max(cables)

ans = 0
while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for cable in cables:
        cnt += cable // mid

    if cnt >= n:
        ans = mid
        start = mid + 1
    else:
        end = mid - 1

print(ans)