백준 1654번 <랜선 자르기>

백준 알고리즘 1654번

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

1654번: 랜선 자르기

---

1654번

입력으로 첫 줄에 이미 가지고 있는 랜선의 수 K와 필요한 랜선의 수 N이 주어진다.

그리고 K개의 이미 가지고 있는 각 랜선의 길이가 들어온다.

 

출력으로는 이미 가지고 있는 랜선들을 나눠 N개를 만들 때 만들 수 있는 랜선의 최대 길이를 정수로 출력하면 된다.

---

문제 해결

문제를 처음 봤을 때 어떻게 풀어야할지 잘 모르겠었다. (아직,, 부족해,,)

알고리즘 분류로 이 문제에 들어와서 이진 탐색을 사용하는 것은 알 수 있었다.

 

이진 탐색으로 이 문제를 어떻게 해결할까 고민을 하다가

이미 가진 랜선의 길이 중 가장 긴 랜선의 길이를 기준으로 이진 탐색을 하면 될 것 같았다.

 

BinarySearch(data, start, end, n)

-> data는 입력으로 들어온 랜선의 길이를 저장하고 있다.

-> start는 탐색할 범위의 시작

-> end는 탐색할 범위의 끝

-> n은 필요한 랜선의 수

 

처음 함수를 호출할 때 이미 가진 랜선의 길이 중 가장 긴 길이를 end에 넣고 start에는 0을 넣으면 된다.

(start + end) / 2의 값을 구해서 몇 개의 랜선을 얻을 수 있는지 계산한다.

 

이때 n보다 작은 경우에는 더 많은 랜선을 얻을 수 있도록 해야 하므로 start는 start로 end는 (start+end) / 2로 함수를 호출한다.

우리는 최대 랜선의 길이를 알고 싶은 것이므로 n보다 크거나 같은 경우는 start를 (start + end) / 2로 end를 end로 하여 함수를 호출한다.

 

종료 조건은 start+1이 end와 같을 때로 (start + end) / 2를 반환한다.

 

이 문제에는 예외 처리를 해줘야 하는 경우가 있는데

1. 이미 가진 랜선의 개수가 1이고 필요한 랜선의 개수도 1일 때

2. 이미 가진 랜선의 개수가 2개 이상이고 모두 같은 길이일 때

이 두 가지의 경우이다.

 

1번의 경우에는 이미 가진 랜선의 길이를 출력해주면 되고

2번의 경우에도 이미 가진 랜선 중 하나의 길이를 출력해주면 된다.

 

사실 이 예외들은 반례를 찾아보다가 알게 된 예외였다.

---

코드

def main():
    k, n = map(int, input().split())

    data = []
    check = False
    for _ in range(k):
        temp = int(input())
        if len(data) != 0 and data[0] != temp:
            check = True
        data.append(temp)
    if n == 1 and k == 1:
        print(data[0])
    elif not check and len(data) > 1:
        print(data[0])
    else:
        maxN = max(data)
        print(BinarySearch(data, 0, maxN, n))

def BinarySearch(data, start, end, n):
    binary = (start + end) // 2
    if start + 1 == end:
        return binary
    temp = 0
    for i in data:
        temp += i // binary
    if temp < n:
        return BinarySearch(data, start, binary,n)
    else:
        return BinarySearch(data,binary, end,n)
main()

---

결과