[코딩테스트 공부] 랜선 자르기
출처: https://www.acmicpc.net/problem/1654
문제 분석
문제의 조건을 보게 되면, 시간 제한은 2초이고, K는 10000 이하로 제한이 되어있습니다. 따라서 O(N^2)까지의 복잡도가 허용된 상황이지만, 이 문제는 이분탐색으로 풀 수 밖에 없습니다. 이유는 다음과 같습니다.
- 데이터의 리스트만으로 특정한 정수 값을 도출해야합니다.
- 특정한 정수 값이 데이터 리스트 안에 존재하는 값이라는 보장이 존재하지 않기 때문에, 다른 방식으로 값을 도출해야합니다.
- 위의 제약 조건들을 분석해보면, 이분탐색이 최적이라는 것을 단박에 알아차릴 수 있습니다.
이 문제는 이전의 나무 자르기 문제와 풀이 방법이 매우 유사합니다. 코드를 확인하겠습니다.
코드를 확인해볼까요?
import sys
input = sys.stdin.readline
K, N = map(int, input().split())
line_length_list = []
for _ in range(K):
line_length_list.append(int(input()))
start, end = 1, max(line_length_list)
# 이분 탐색 시작
while start <= end:
sum = 0
mid = (start + end) // 2
for length in line_length_list:
sum += length // mid
if sum >= N:
start = mid + 1
else:
end = mid - 1
print(end)
이전의 나무 자르기 문제와 풀이 방법이 똑같기 때문에, 간단하게만 설명드리겠습니다.
start는 1, end의 경우 랜선의 최대 길이로 잡고, 이분 탐색을 시작합니다.
랜선의 경우, mid의 값으로 나눈 나머지만큼 챙길 수 있기 때문에 length에 mid를 나눈 몫 만큼을 sum에 반영합니다.
sum의 값에 따라서, start 혹은 end의 값을 조절해주면 됩니다.
- sum이 N 이상일 경우 : 조금 더 길게 잘라도 되니까 start의 값을 조절
- sum이 N 미만일 경우 : 조금 더 짧게 잘라야하기 때문에 end의 값을 조절
따라서, 마지막에는 end를 출력하면 문제는 해결됩니다.
Author And Source
이 문제에 관하여([코딩테스트 공부] 랜선 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@18k7102dy/coding-test-fourth-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)