Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 1654 랜선 자르기
백준 1654 랜선 자르기
문제
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다.
박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠 영식이에게 도움을 청했다.
이미 오영식은 K개의 랜선을 가지고 있지만, 이 랜선의 길이가 제각각이다.
박성원은 랜선을 모두 N개의 같은 길이 랜선으로 만들고 싶기 때문에 K개의 랜선을 잘라 만들어야 한다.
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하고, 기존의 K개 랜선으로 N개의 랜선을 만들 수 없는 경우는 존재하지 않는다 가정한다.
또한 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다 가정하자.
N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
입력
- 첫 번째 줄: 이미 가지고 있는 랜선 수 K, 필요한 랜선 갯수 N
- 두 번재 줄 ~ : 각 랜선의 길이
출력
N개를 만들 수 있는 랜선의 최대 길이
해결 방식
이진 탐색 알고르즘
- (최대값) // 2 부터 mid로 대입하여 탐색 시작
- n 보다 큰 경우: 나눈 길이가 너무 짧은 경우
- 현재 mid값보다 작은 숫자들도 이와 같은 상황일 것 → 탐색하지 않도록 설정해야 한다.
- start = mid + 1로 설정 후 다시 탐색 시작
- n 보다 작은 경우: 나눈 길이가 너무 긴 경우
- 현재 mid값보다 큰 숫자들도 이와 같은 상황일 것 → 탐색하지 않도록 설정
- end = mid - 1로 설정 후 다시 탐색 시작
- n 보다 큰 경우: 나눈 길이가 너무 짧은 경우
- 가장 길게 자를 수 있는 길이(end) 출력
코드
import sys
input = sys.stdin.readline
k, n = map(int, input().split())
cables = list(int(input()) for _ in range(k))
start = 1
end = max(cables)
while start <= end:
mid = (start + end) // 2
result = 0
for cable in cables:
result += (cable // mid)
if result >= n:
start = mid + 1
elif result < n:
end = mid - 1
print(end)
