알고리즘 자료구조
1654번 랜선자르기 파이썬
Zeta050525
2021. 12. 16. 20:48
728x90
문제
입력과 출력
내가 시도한 풀이
없다. 이다음 줄부터는 내가 징징대는거니까 다음 쪽으로 넘어가도 좋다.
머리가 그냥 멍해졌다.
진짜 어떻게풀지?
이분탐색은 그냥 배열에서 원소를 선형탐색보다 빨리 찾을 수 있는거 아니었나?..
일단 저게 이분탐색으로 풀수가있는건가?..
30분정도 고민하다가 구글의 도움을받았다.
구글의 도움을 받아서 틀은 잡혔지만
그래도 멍했다... 진짜 미칠거같았당...
풀이
start 1
end를 입력받은 케이블 중 가장 긴 케이블의 길이
이렇게 잡아놓고 길이로 이분탐색을 합니다.
4 11
802
743
457
539
가장 긴 랜선은 802
803 //2
401
길이 802의 랜선은2개 자를수있고
743은 1개
457도 1개
539도 1개
총 5개
근데 성원이가 가져가려는 개수는 11개인데
우리가 더 적게 잘랐죠
그럼 길이를 높여야할까요 내려야할까요?
내려야합니다.
end = mid -1
약간 감이 오시죠 이제
코드
K , N = map(int , input().split(" "))
Cable = [int(input()) for _ in range(K)]
start = 1
end = max(Cable)
while start <= end:
count = 0
mid = (start+end)//2
for i in Cable:
count += i//mid #mid값으로 자른 갯수
if count >= N: #N이 11이고 mid값으로 자른 갯수가 14거나 그러면 길이를 늘려줍니다
start = mid + 1 #근데 같아도 올림 이건 아래 글에서 설명할게요
else:
end = mid - 1
print(end)
? 왜 count == N
break
print(mid)를 하지 않는거지?
if count >= N: 같은경우에도 위 높이를 올리지?
할수도있는데 성원이가 가져갈수있는길이랑
딱 떨어지지 않을수도있고
최대값을 구해야하기때문에
mid가 198인경우
802 //198 4개
743//198 3개
457 // 198 2개
539 //198 2개
4+3+2+2
얘도 11개네요
근데 최대값을 구하라고했으니까
이렇게 갯수가 딱 떨어져도
길이를 늘려줍니다.
결국 최대값에 도달했을때는
end = mid - 1밖에못하고
while 문을 탈출하게되면서
end값이 최대 길이가 되는겁니다.
파이썬으로 제출하는데 자꾸 시간초과나면서
아니 맞는데왜틀리지가 계속 나오면 진짜 맞는데 파이썬이라 시간초과가 나오는 걸수도있습니다.
ㅠㅠ
728x90