문제
출처
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
입력 4 11 802 743 457 539출력 200
문제 정리
- 캠프 때 쓸 N개의 랜선을 만들어야 한다.
- K개의 랜선을 가지고 있지만 길이는 제각각일수도 있고 같을 수도 있다.
- 이미 자른 랜선은 붙일 수 없다.
- 랜선을 자르거나 만들 때 손실되는 길이는 없다.
개수에 맞게 만들 수 있는 랜선의 최대 길이는 일단 생각할 수 있는 것은 모두 정렬하는 것
그리고 만들어질 수 있는 가장 짧은 선인 1과 가장 긴 선인 가장 긴 랜선 사이에서 탐색을 진행하면 된다는 점이다.
물론 가장 긴 랜선에서 1개로 나눈 것과 N개로 나눈것의 사이에 최대 길이가 되는 값이 존재할 것이라는 접근도 괜찮겠지만
시간 차이가 많이 나지 않을 뿐더러 Division Error가 날 수 있고 예외처리를 하다보면 코드가 직관적이지 않게 되는 점이 있기에 start(가장 짧은 선)는 1로 시작하는 것이 좋다. 랜선은 무조건 1 이상이기에 그렇다.
문제 풀이
k, n = map(int, input().split()) # k개(보유 랜선 수), n개(만들어야 하는 랜선 수)
lan_cables = [] # 보유 랜선의 길이값들
for _ in range(k):
lan_cables.append(int(input()))
lan_cables.sort() # 가장 긴 길이를 찾기 위해 정렬
start = 1
end = end = lan_cables[-1]
max_length = 0
# 이분 탐색 진행
while start <=end: # 종료 조건 탐색이 끝난 경우
# mid값 업데이트
mid = (start + end) // 2
count = 0 # 랜선이 몇 개 만들어지는가
for cable in lan_cables:
count += cable // mid
if count >= n: # n개 이상 만드는 경우는 필요 이상으로 만들어지기에 자르는 길이를 좀 더 길게 진행
max_length = max(mid, max_length) # n개 이상 만들어지는 선들 중 max_length 업데이트
start = mid + 1
else : # n개를 만들 수 없는 경우는 선이 너무 길다는 의미
end = mid -1
print(max_length)종료 조건은 가능한 모든 길이를 이분적으로 탐색하는 것으로 설정했다.
start가 end보다 클때 종료가 되는 것이다.
문제 후기
이 문제는 어렵게 접근하면 어려운 문제 같다. 좀 더 쉽고 간단하게 접근해야 하는 듯 하다.
이분 탐색은 정렬 이라는 인식이 있어서 처음에 불필요하게 리스트를 따로 만들어 랜선 후보값들을 저장했는데 메모리 초과가 떴다.
종료 조건도 따로 설정하지 않고 그저 탐색이 끝나는 경우로 하니 간단했다.
전형적인 이분탐색 문제가 아닐까 싶다.
