1654 - 랜선 자르기

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

1654번: 랜선 자르기

import sys
input = sys.stdin.readline

klen, n = map(int, input().split())
k = list()
for _ in range(klen):
    k.append(int(input()))

def check(x):
    s = 0
    for i in range(klen):
        s += (k[i] // x)
    
    if s >= n:
        return True
    else:
        return False

start = 1
end = max(k) #max로 수정

while start + 1 < end:
    mid = (start + end) // 2
    
    if check(mid):
        start = mid
    else:
        end = mid

if check(end):
    print(end)
else:
    print(start)

 

- Brute force

- 이분 탐색 (매개 변수 탐색)

 

브루트 포스 썼다가 시간 초과났다..

 

그래서 이분 탐색으로 접근했는데, 먼가 답이 잘 안나와서 알고리즘 분류 보니 '매개 변수 탐색'이라는 못 보던 알고리즘이 있어서 구글링햇음

 

주어진 조건을 만족하는 최대값을 이분 탐색을 통해 찾는.. 알고리즘 이었는데 거의 이분 탐색이랑 비슷해서 이해하는데 어려움은 없엇다

 

하지만 개빢치는건 end값을 min(k)로 잡아서

2 4
100
1

이런 테스트케이스를 돌리면 1이 나왔다

그걸 모르고 7번 제출해서 다 틀렷다ㅋㅋ 노얼탱스

 

그래도 end값 정할 때 고려해야할 점 하나 배워서 기분 좋고

로직 짜는데 재밌었따