[99클럽] 이분탐색

b1654

 

---

 

☄️ 풀이 전 내 생각

1. 현재 알고있는 자료구조인 배열, 스택, 해시에서는 제대로 답을 낼 수 없는 구조라고 생각이 들었다.
2. 주어진 랜선의 총합도 구해보고 나누기도 시도해봤지만 어떻게 풀어야할지 제대로 감이 잡히질 않아서 답지를 보면서 분석하기로 했다.
3. 예제를 보면 답이 200인걸 알 수 있는데 1부터 시작해서 200까지 올라가면서 11이 나오지 않는 경우를 찾는 거라면 너무 시간이 오래걸릴 것 같아서 아닌 것 같다.

소요시간: 50분

 

---

🌈 파이썬 코드

import sys

# 가지고 있는 랜선의 개수 k , 필요한 랜선의 개수 n

k, n = map(int, input().split(" "))
lines = []
for _ in range(k):
    line = int(input())
    lines.append(line)

def solution(lines, n):
    
    start, end = 1, max(lines)
    while start <= end:
        mid = (start + end) // 2
        line_cnt = 0
        for line in lines:
            line_cnt += line // mid
        if line_cnt >= n:
            start = mid + 1
        else:
            end = mid - 1
        pass
        
    return end

print(solution(lines, n))

• 이분탐색에 대해서 개념으로는 어느정도 이해를 했는데 코드로 구현하는 과정에서 아직은 좀 부족함을 느낀다. 이와 관련된 다른 예제 문제는 꼭 몇 번 풀어봐야겠다.