본문 바로가기
Coding Test (코딩 테스트)

[class2]백준 1654번(랜선 자르기) - 코딩테스트 22일차(2025.02.12)

by BioLearner 2025. 2. 12.
반응형

문제유형

이분 탐색

풀이 방법 도출 과정

1. 이 문제는 단순한 구현 문제처럼 보일 수 있지만, 이를 구현하는 방식에 따라 시간 복잡도가 커질 수 있다.

2. 따라서, 문제를 해결할 수 있는 더 효율적인 방법을 찾아야 한다. 이를 위해 이분 탐색을 활용하는 방식으로 접근하려 한다.

3. 이분 탐색을 적용하기 위해, 첫 번째로 left를 1로 설정하고, right는 주어진 랜선들의 길이 중에서 가장 긴 값으로 설정한다. 이렇게 설정하는 이유는 랜선 길이가 1부터 가장 긴 값까지 범위 안에 존재하기 때문이다.

3. 그 다음, 중간값인 mid를 계산한다. 그리고 mid 길이로 랜선을 나누었을 때, 얻을 수 있는 랜선의 개수가 주어진 N개 이상이 되는지 확인한다. 이 조건을 만족하는지 여부에 따라 이분 탐색을 반복하여 최적의 값을 찾는다.

 

시간 복잡도

입력 받기 O(K)

이분 탐색 log(max(lan))

각 반복에서의 연산 O(K)

 

다 합해서 O(K * log(max(lan)))이다.

코드 및 간단설명

이분탐색을 사용하여 문제를 풀었다.

def binary_search(lan, N):
    left, right = 1, max(lan)
    
    while left <= right:
        mid = (left + right) // 2
        lines = 0
        for i in lan:
            lines += i // mid
        
        if lines >= N:
            left = mid + 1
        else:
            right = mid - 1
    
    return right

# 입력 받기
K, N = map(int, input().split())
lan = [int(input()) for _ in range(K)]

# 이분 탐색 함수 호출 및 결과 출력
print(binary_search(lan, N))

 

반응형