파이썬 Python | 알고리즘 | 백준 랜선 자르기

⭕ 파이썬 Python | 알고리즘 | 백준 랜선 자르기

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• K개의 랜선을 N개의 동일한 길이로 잘라야 하는데, 그중에서 가능한 랜선의 최대 길이를 구하는 것이 목적이다. 이때 필요한 랜선의 수 N보다 많이 만들어도 상관없다. 따라서 이 문제는 "N개 이상의 랜선을 만들 수 있는 최대 길이"를 구하는 문제로 정의할 수 있다.
• 단순한 방법으로 접근하였을 때, 가장 긴 랜선의 길이에서부터 하나씩 줄여가면서 N개 이상의 랜선을 만들 수 있는지 확인하려고 하였다. 랜선의 길이가 수백만까지 커질 수 있기 때문에, 매번 확인하는 방식으로는 시간 내에 문제를 해결할 수 없었다.
• 범위 내에서 최대값을 찾는 문제이므로, 이진 탐색을 통해 해결할 수 있다. 1cm부터 가장 긴 랜선의 길이까지의 범위를 탐색하면서, 해당 길이로 N개의 랜선을 만들 수 있는지 확인하면 된다.

 

➡️ 코드 설계하기

1. 탐색 범위의 최소값은 1cm, 최댓값은 주어진 랜선 중 가장 긴 랜선의 길이로 설정한다.
2. 중간값(mid)을 계산한 뒤, 이 길이로 N개 이상의 랜선을 만들 수 있는지 확인한다.
3. 만약 만들 수 있다면, 더 긴 랜선도 만들 수 있을지 확인하기 위해 범위를 키우고(start = mid + 1), 그렇지 않다면 범위를 줄인다(end = mid - 1).
4. 이 과정을 반복하여 최종적으로 가능한 최대 랜선 길이를 구한다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회 차 

• 시간 116ms
• 이진 탐색은 탐색 범위를 절반씩 줄여나가기 때문에 시간 복잡도는 O(log L)이다. 여기서 L은 가장 긴 랜선의 길이이다. 또한, 각 단계에서 K개의 랜선에 대해 잘라낼 수 있는 개수를 계산하므로, 이 과정의 시간 복잡도는 O(K)이다. 따라서 전체 시간 복잡도는 O(K * log L)로 매우 효율적이다.
• 처음에는 순차적으로 접근했으나, 이 방법은 비효율적임을 깨달았고, 이진 탐색을 사용하여 문제를 해결하였다. 이진 탐색을 통해 범위를 절반씩 줄여가면서 최적의 해를 찾아내는 것이 이 문제의 핵심 해결 방법이다.

K, N = map(int, input().split())
lan_lengths = [int(input()) for _ in range(K)]

start = 1
end = max(lan_lengths)
result = 0

while start <= end:
    mid = (start + end) // 2
    count = sum(length // mid for length in lan_lengths)
    
    if count >= N:  # N개 이상의 랜선을 만들 수 있는 경우
        result = mid  # 가능한 길이로 저장
        start = mid + 1  # 더 긴 길이를 탐색
    else:
        end = mid - 1  # 더 짧은 길이를 탐색

print(result)

 

➡️ 정답 코드

K, N = map(int, input().split())
lan_lengths = [int(input()) for _ in range(K)]

start = 1
end = max(lan_lengths)
result = 0

while start <= end:
    mid = (start + end) // 2
    count = sum(length // mid for length in lan_lengths)
    
    if count >= N:  # N개 이상의 랜선을 만들 수 있는 경우
        result = mid  # 가능한 길이로 저장
        start = mid + 1  # 더 긴 길이를 탐색
    else:
        end = mid - 1  # 더 짧은 길이를 탐색

print(result)