[Python] 1654번 랜선 자르기

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

1654번: 랜선 자르기

---

22/08/26

 

클래스 2 문제 중 안 푼 문제가 있길래 푼 문제이다.

 

전형적인 이분탐색 문제이고, 이분탐색 문제 특성상 범위나 종료 조건을 잘못 설정하면 맞왜틀을 하기 쉽기 때문에 나도 맞왜틀을 여러 번 했다.

 

당연히 이분탐색이 무엇인지 알고 있다는 전제 하에서 글이 쓰여있으므로, 풀이를 참고할 생각이 있다면 이분 탐색기법을 알아야 할 것이다.

---

 

문제 접근 방법:

 

 

기존의 가지고 있는 K개의 랜선들을 일정한 간격으로 잘라 총 N개 이상의 랜선을 만들고자 하는 것이 목표인데, 이 중 최대 길이를 찾는 것이 우리의 목적이다.

 

편의상 K개의 랜선들의 리스트를 wires라고 부르자.

 

당연히 랜선의 길이로 들어올 수 있는 숫자는 2^31 - 1까지 들어올 수 있기 때문에 1부터 시작하여 max(wires)까지 돌려가며 일일이 확인하면 무조건 시간 초과가 날 것이라고 생각했다.

 

때문에 이분 탐색 기법으로 최대 길이를 찾으면 아무리 길어도 31번 안에는 찾을 수 있을 것이라고 생각 했기 때문에 이분 탐색을 선택하게 되었다.

 

먼저 랜선을 일정 길이로 자른다.

 

그러면 두가지 선택지가 나뉘는데,

---

1. 랜선의 개수가 N보다 작다

-> 이 경우 랜선 한 도막을 너무 길게 자른 것이므로 좀 더 짧은 길이로 탐색해본다

 

2. 랜선의 개수가 N보다 크거나 같다

-> 이 경우, 조건을 만족하긴 하지만 우리가 원하는 것은 이 조건을 만족한 뒤에, 최대 길이를 구하는 것이므로 최대 길이를 구할 때까지 다시 탐색해본다.

---

그러면, 이제 종료조건이 문제가 되는데, 이 종료 조건을 설정할 때 조금 이리저리 헤맸다.

 

처음으로 접근했을 때는 랜선의 개수가 N과 같을 때 종료하는 것으로 했는데 반례가 나와버려 실패해 버렸고,

 

두 번째로 접근했을 때는 전형적인 이분 탐색의 종료 조건으로, 이분 탐색을 하다가 low가 high보다 크거나 같을 때로 했는데 그것 또한 실패했다고 나왔다.

 

결국 마지막으로 접근했을 때에는 두 번째 접근 방식을 살짝 고쳐서 low가 high보다 클 때로 종료 조건을 만들었는데, 이 코드가 맞았습니다로 통과되었다.

 

---

다음은 이분 탐색을 재귀 함수로 짜서 맞았습니다를 받은 나의 코드이다. 더보기를 누르면 확인할 수 있다.

 

# 1654번 랜선 자르기
# 이분 탐색, 매개 변수 탐색
import sys
input = sys.stdin.readline

K, N = map(int, input().split())
wires = [int(input()) for _ in range(K)]
def binary_search(low, high, N, arr):
    if low > high:
        return high
    mid = (low+high)//2
    total = 0
    for wire in arr:
        total += (wire//mid)
    if total >= N:
        return binary_search(mid+1, high, N, arr)
    else:
        return binary_search(low, mid-1, N, arr)

print(binary_search(1, max(wires), N, wires))