[1654] 랜선 자르기(python)

1. 문제

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

1654번: 랜선 자르기

2. 접근 방법

* 문제 이해

- 길이가 다른 k개의 랜선을 잘라서, N개 이상의 같은 길이 랜선들로 만들 때 (자르고 남는 대상은 버림) 만들 수 있는 최대 길이

 

* 접근 순서 

    1) 최대 길이 찾기(최적의 길이 찾기) : 최적 해를 구하는 것이므로 탐색(?)의 느낌이 남...  탐색에서 가장 대표적인 예시는 이분 탐색! 

 

    2) 탐색 시작 방향 구하기 : 가장 짧은 길이가 1cm <-> 가장 긴 길이는 N=1일때 가장 긴 랜선 길이.  즉, 아무리 길게 만들려 해도 기존 랜선의 가장 긴 길이보다 길게 만들 순 없음. 가장 긴 랜선 길이에서부터 탐색을 시작해보기. 

 

    3) 예시 적용해보기 :  만들려 하는 길이를 L이라 하면, 다음의 방식으로 계산하면서 답 도출 가능 

                               L = 400 ( (0 + 800) / 2 )    ---> 5개 랜선이 생성됨 (x)

                               L = 200 ( (0 + 400) / 2 )    ---> 11개 랜선이 생성됨 (o)

                               L = 300 ( (200 + 400) / 2 ) ---> 6개 랜선이 생성됨 (x)

                               L = 250 ( (200 + 300) / 2 ) ---> 7개 랜선이 생성됨 (x) 

                                           

3. 실수했던 부분 & 처음 알았던 부분

1) 파이썬으로 이분 탐색 

start = 1
end = max(data)-1
mid = 0
while start <= end:
	mid = (start + end) // 2
    result = ~~~
    if result == N: #원하는 답을 구했을 때
    	print(result)
        break
    elif result < N: #원하는 답보다 더 작은 값이 나올 때
    	start = mid + 1
    else
    	end = mid - 1

 - start값으로 0이 들어가지 않는 것이 좋을 것 같다 ( mid = (start + end) / 2할 때 zero에러 날 수 있음)

 - 보통 이분탐색에서 start, end는 정렬된 리스트의 시작 & 끝 값

 

2) 1차원 배열 for문으로 입력받기

#1번 방식
arr=[] for i in range(n): arr.append(int(input()))

#2번 방식
arr = []
for i in range(N):
	arr = append(int(input())

 - 2번 방식 : arr = append(map(int, input())) --- (X)

                 max(arr)에서 TypeError: unorderable types: map() > map() 발생  <- 정확한 분석은 따로 정리 필요

 

3) 이분탐색에서 최대값 구하기

-  count == N일때 return하도록 했었는데, 그러게 하면 최대 길이를 구할 수 없음

   => { count == N, count < N, count > N } 3가지 경우로 나누지 말고

        { count >= N, count < N} 2가지 경우로 나누고 count >= N일 때의 mid값 저장해놓기 

 

4) tab / space에러 찾기 어려울 때

   vim에서 space 4개 -> tab으로 변경하기

   =>  esc(명령어 모드 변경 후) %s/    /\t/g : 

 

 

4. 코드

 

#변수 선언 
K, N = map(int,input().split())
arr = []

for i in range(K):
	arr.append(int(input()))

#가장 긴 길이 기준으로 이분 탐색
start = 1
end = max(arr)
result = 0

while start <= end:
	mid = (start + end ) // 2 
	count = 0 
	
	#길이가 mid인 랜선으로 자를 때 만들 수 있는 랜선 개수 탐색
	for i in arr:
		count += ( i // mid )
	 
	#랜선 개수가 N이 될 때까지 탐색 진행
	if count >= N:
		result = mid
		start = mid + 1
	else:
		end = mid - 1

print(result)