[백준] 1654 파이썬(python) : 랜선 자르기 - (★)

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

1654번: 랜선 자르기

 

 

22.08.06 수정)

import sys
n, m = map(int, sys.stdin.readline().split())
lan = [ int(sys.stdin.readline()) for _ in range(n) ]
start, end = 1, max(lan) #1
res = 0
while start <= end: #2
    mid = (start+end) // 2 #3
    cnt = 0
    for i in lan:
        cnt += (i // mid) #4
    if cnt >= m: #5
        res = mid #6
        start = mid + 1
    else: #7
        end = mid - 1
print(res)

 

#1 : 시작값은 1이고 끝값은 배열 중 가장 긴 값이다.

#2 : start가 end를 추월하거나 같아지면 반복종료

#3 : mid는 start와 end의 중간값(여기서 mid는 랜선을 자르는 길이)

#4 : 랜선들중 mid로 자른 개수들의 합이 lines

(300에서 140 짜리 2개를 만들고 남은 20은 버리니까 몫만 챙기고 나머지는 버린다.)

#5 : lines가 의도한 n보다 같거나 많다면 mid값이 왼쪽에 치우쳐져 있는것이니까 start값을 증가시켜 mid를 조정

원하는 개수n보다 더 많이 자르게 되어도 n만큼 자른것과 같다고 했으니까 '>=' 로 설정

#6 : #5이 의도하는 상황이니까 그때의 랜선의 길이가 최선의 길이이고 갱신하면서 정답이 됨 

#7 : 그 반대라면 end를 감소시켜 mid값을 조정

 

 

예전에 한번 풀어봤던 이분탐색 문제랑 비슷한 문제다. 하지만 접근방법이 떠오르지 않았다. 이분탐색은 큰 틀은 같고 거기서 조금씩 문제에서 원하는 답을 구하기 위해 변형을 가해주는데 함수형으로 작성해서 재귀함수로 풀 수도 있고 위 처럼 반복문으로도 해결할 수 있다. 이분탐색 문제 좀 더 적응해야 할것 같다.

 

 

2805번 나무 자르기(https://hgk5722.tistory.com/145)