[백준] 1654번 : 랜선 자르기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 처음 가지고 있는 랜선의 개수에서 필요한 랜선의 개수만큼 생기도록 랜선을 자를 때, 만들 수 있는 랜선의 최대 길이를 구하는 문제이다.

처음 가지고 있는 랜선의 길이에서 만들 수 있는 랜선의 최소 길이와 최대 길이를 정한 후, 그 중간 길이를 구하여 각 랜선을 중간 길이로 잘라 개수를 세어준다.

만약 랜선의 개수가 필요한 랜선의 개수보다 적으면, 기준이 되는 중간 길이가 더 짧아야 하므로 최대 길이를 중간 길이 이전으로 변경한다.

반면에 랜선의 개수가 필요한 랜선의 개수보다 많거나 같으면, 기준이 되는 중간 길이가 더 길어도 되므로 최소 길이를 중간 길이 다음으로 변경한다.

최소 길이가 최대 길이를 넘기 전까지 반복한다.

위 같은 과정을 이분 탐색 알고리즘이라고 하며 해당 문제는 이분 탐색 알고리즘을 활용하면 해결할 수 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 처음 가지고 있는 랜선의 개수와 필요한 랜선의 개수를 입력받는다. K, N = map(int, sys.stdin.readline().split())
3. 처음 가지고 있는 랜선의 길이를 저장할 리스트를 생성한다. li = []
4. 처음 가지고 있는 랜선의 개수만큼 반복하며 각 랜선의 길이를 입력받아 리스트에 추가한다. for _ in range(K): li.append(int(sys.stdin.readline()))
5. 만들 수 있는 랜선의 최소 길이 1을 변수에 저장한다. MIN = 1
6. 가지고 있는 랜선에서 최대 길이를 만들 수 있는 랜선의 최대 길이 변수에 저장한다. MAX = max(li)
7. 최소 길이가 최대 길이를 넘기 전까지 반복한다. while (MIN <= MAX)
   1. 최소 길이와 최대 길이로 랜선을 자르는 기준인 중간 길이를 구한다. mid = (MAX + MIN) // 2
   2. 중간 길이를 기준으로 랜선을 잘랐을 때 생기는 랜선의 개수를 저장할 변수를 생성하고 초기화한다. count = 0
   3. 처음 가지고 있던 랜선들을 하나씩 불러오며 랜선을 잘라 생기는 랜선의 개수에 해당 랜선을 중간 길이에 맞춰 잘랐을 때 나오는 랜선의 개수를 더해준다. for l in li: count += (l // mid)
   4. 만약 생긴 랜선의 개수가 필요한 랜선의 개수보다 작으면, 기준이 되는 중간 길이가 더 짧아야 하므로 최대 길이를 중간 길이 이전으로 변경한다. if (count < N): MAX = mid - 1
   5. 반면에 생긴 랜선의 개수가 필요한 랜선의 개수보다 크거나 같으면, 기준이 되는 중간 길이가 더 길어도 되므로 최소 길이를 중간 길이 다음으로 변경한다. else: MIN = mid + 1
8. 최소 길이가 최대 길이를 넘어 반복문이 종료된 후 최대 길이가 만들 수 있는 랜선의 최대 길이가 된다. print(MAX)

3. 소스코드

import sys

K, N = map(int, sys.stdin.readline().split())
li = []
for _ in range(K):
    li.append(int(sys.stdin.readline()))

MIN = 1
MAX = max(li)

while (MIN <= MAX):
    mid = (MAX + MIN) // 2
    count = 0

    for l in li:
        count += (l // mid)

    if (count < N):
        MAX = mid - 1
    else:
        MIN = mid + 1

print(MAX)