백준 - 1654번 랜선 자르기 python 문제풀이 [Hellfer]

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

1654번: 랜선 자르기

🔷 알고리즘 분류 - 이분 탐색, 시간 복잡도 O(logN)   

난이도 - 실버 2

이분 탐색(Binary Search)은 정렬된 데이터셋에서 특정 값을 효율적으로 찾는 알고리즘입니다. 

이 알고리즘의 이름에서 알 수 있듯이, 이분 탐색은 데이터셋을 '두 부분'으로 나누는 방식으로 작동합니다.

기본 원리는 다음과 같습니다:

1. 데이터셋의 중앙값을 선택합니다.

2. 선택한 중앙값이 찾고자 하는 값인지 확인합니다.

3. 찾고자 하는 값이 중앙값보다 크다면, 데이터셋의 오른쪽 부분을 대상으로 다시 탐색합니다.

4. 찾고자 하는 값이 중앙값보다 작다면, 데이터셋의 왼쪽 부분을 대상으로 다시 탐색합니다.

5. 이 과정을 반복하면서 찾고자 하는 값을 찾습니다.

 

탐색 문제: 정렬된 배열이나 리스트에서 특정 값을 빠르게 찾는 문제에 이분 탐색을 사용할 수 있습니다. 

이는 배열이나 리스트의 크기가 크더라도 로그 시간 복잡도를 가지므로 매우 효율적입니다.

최적화 문제: 이분 탐색은 최적의 값을 찾는 최적화 문제에도 사용될 수 있습니다. 

예를 들어, 숫자 범위 내에서 특정 조건을 만족하는 가장 큰(또는 작은) 값을 찾는 문제 등에 이분 탐색을 활용할 수 있습니다.

 

아래는 이분 탐색 알고리즘의 기본 구조 코드입니다.

 

def binary_search(array, target):  # 이진 탐색 함수 정의. array는 탐색 대상 리스트, target은 찾고자 하는 값
    start = 0  # 시작점을 리스트의 첫번째 인덱스로 설정
    end = len(array) - 1  # 끝점을 리스트의 마지막 인덱스로 설정

    while start <= end:  # 시작점이 끝점보다 작거나 같은 동안 반복
        mid = (start + end) // 2  # 중간점을 계산 (시작점과 끝점의 중간)

        if array[mid] == target:  # 중간점의 값이 찾고자 하는 값이라면
            return mid  # 중간점의 인덱스 반환
        elif array[mid] < target:  # 중간점의 값이 찾고자 하는 값보다 작다면
            start = mid + 1  # 시작점을 중간점보다 하나 뒤로 이동
        else:  # 중간점의 값이 찾고자 하는 값보다 크다면
            end = mid - 1  # 끝점을 중간점보다 하나 앞으로 이동

    return None  # 탐색 대상이 리스트에 없는 경우 None 반환

🔶문제풀이 - 이분 탐색을 이용한 풀이,  시간 복잡도 O(logN)

import sys  # sys 모듈 임포트
input=sys.stdin.readline  # 입력을 빠르게 받기 위한 설정

n,m=map(int,input().split())  # n과 m을 입력받음 (n: 랜선의 개수, m: 필요한 랜선의 개수)
x = []  # 랜선의 길이를 저장할 리스트 초기화
for _ in range(n):  # n번 반복
    x.append(int(input()))  # 각 랜선의 길이를 입력받아 리스트에 추가
    
start, end=1, max(x)  # 이진 탐색의 시작점을 1, 끝점을 가장 긴 랜선의 길이로 설정

while start<=end:  # 시작점이 끝점보다 작거나 같은 동안 반복
    mid=(start+end)//2  # 중간값 계산
    len=0  # 자른 랜선의 길이를 저장할 변수 초기화
    for i in x:  # 각 랜선에 대하여
        len+=i//mid  # 랜선을 중간값으로 자른 후의 길이를 len에 더함
        
    if len>=m:  # 자른 랜선의 길이가 필요한 랜선의 길이보다 많거나 같다면
        start=mid+1  # 시작점을 중간값보다 1 큰 값으로 설정
    else:  # 자른 랜선의 길이가 필요한 랜선의 길이보다 적다면
        end=mid-1  # 끝점을 중간값보다 1 작은 값으로 설정
        
print(end)  # 가능한 최대 랜선의 길이 출력

🔶 문제 이해하기

while start<=end:  # 시작점이 끝점보다 작거나 같은 동안 반복
    mid=(start+end)//2  # 중간값 계산
    len=0  # 자른 랜선의 길이를 저장할 변수 초기화
    for i in x:  # 각 랜선에 대하여
        len+=i//mid  # 랜선을 중간값으로 자른 후의 길이를 len에 더함
        
    if len>=m:  # 자른 랜선의 길이가 필요한 랜선의 길이보다 많거나 같다면
        start=mid+1  # 시작점을 중간값보다 1 큰 값으로 설정
    else:  # 자른 랜선의 길이가 필요한 랜선의 길이보다 적다면
        end=mid-1  # 끝점을 중간값보다 1 작은 값으로 설정

 

랜선의 개수 K는 4개, 필요한 랜선의 개수 N은 11개라고 가정하겠습니다. 

각 랜선의 길이는 802, 743, 457, 539입니다.

이진 탐색의 시작점 start는 1, 끝점 end는 가장 긴 랜선의 길이인 802로 설정합니다.

첫 번째 while 루프에서, 중간값 mid는 (1 + 802) // 2 = 401이 됩니다. 각 랜선을 중간값으로 나눈 몫을 len에 더하면, len는 802//401 + 743//401 + 457//401 + 539//401 = 2 + 1 + 1 + 1 = 5가 됩니다.

이 경우 len는 필요한 랜선의 개수 N=11보다 작으므로, 끝점 end를 중간값 mid - 1인 400으로 조정합니다.

다음 while 루프에서, 중간값 mid는 (1 + 400) // 2 = 200이 되고, len는 802//200 + 743//200 + 457//200

+ 539//200 = 4 + 3 + 2 + 2 = 11이 됩니다.

이 경우 len는 필요한 랜선의 개수 N=11과 같으므로, 시작점 start를 중간값 mid + 1인 201로 조정합니다.

이런 식으로 while 루프를 반복하면서 시작점과 끝점을 조정하다 보면, 결국 랜선을 자를 수 있는 최대 길이를 찾을 수 있습니다. 이 경우, 랜선을 자를 수 있는 최대 길이는 200이 됩니다.

 

🤗파이팅입니다~ 여러분!!🤗