문제
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
예제 입력
4 11
802
743
457
539
예제 출력
200
풀이
이분 탐색의 개념은 알았는데, 어렵게 생각해서 푸는데 오래걸렸다. 모든 케이스를 일일이 조건별로 예외처리를 했는데 일반적인 풀이 방법이 있었다. 앞으로 일반적인 풀이를 염두에 두고 이분 탐색을 사용해야겠다.
그리고 재귀보다는 반복문을 이용해서 푸는게 쉬운 것 같다.
첫번째 풀이(재귀 + 조건별 예외 처리)
재귀를 이용하면 일반적으로 return 문으로 결과값을 반환하는데 나는 print 문을 이용했다. 별로 좋지 않은 것 같다. 재귀를 이용할땐 return 문으로 결과값을 반환하도록 하자.
# 랜선 자르기
k, n = map(int, input().split())
arr = []
for _ in range(k): arr.append(int(input()))
arr.sort()
# 몫의 합을 계산하는 함수
def funcSum(n):
sum = 0
for i in range(k):
sum += arr[i]//n
return sum
# 이분 탐색 시작
def binarySearch(start,end):
global n
mid = (start + end)//2
res = funcSum(mid)
# 내가 찾던 개수와 동일할때
if res == n:
if start == end: # 길이 1인 경우 그게 답임
print(mid)
else: # 아직 길이 더 남은 경우 -> 현재~오른쪽 끝까지 이분탐색 실시
if res == funcSum(mid+1):
binarySearch(mid+1, end)
else: print(mid)
# 내가 찾던 개수와 같지 않을때
elif res < n: # 더 적은 경우 -> 무조건 같거나 많은 경우가 존재함
binarySearch(start, mid-1) # 다시 돌림
elif res > n: # 더 많은 경우
if funcSum(mid+1) < n: # 더 많지만 이게 최선인 경우
print(mid)
else: # 길이 1 아닌 경우 ->
binarySearch(mid+1,end)
return
binarySearch(1,arr[k-1])두번째 풀이(반복문)
이 방법을 이용하면 mid로 나눈 몫들의 합, 즉 만들 수 있는 랜선의 개수가 목표치와 같거나 클 경우 mid+1로 나눴을때의 경우도 목표치와 같거나 클 수 있기 때문에 start = mid+1 로 진행해준다.
이렇게 진행했을 경우, 만약 start(mid+1) ~ end 사이에 구하고자 하는 mid가 없는 경우 end = mid - 1 가 반복되기 때문에 결국 end가 start보다 한칸 앞에 위치하게 된다. 그러면 반복문이 종료되기 때문에 기존의 mid가 정답인 것을 알게 된다.
만들 수 있는 랜선의 개수가 목표치보다 작은 경우는 무조건 목표치를 만족시키는 값이 있어야 하기 때문에 end = mid - 1 을 해주면 된다.
k,n = map(int,input().split())
arr = [int(input()) for _ in range(k)]
start, end = 1, max(arr)
while start <= end:
mid = (start+end)//2
cnt = 0
for v in arr:
if v >= mid:
cnt += v//mid
if cnt >= n:
start = mid + 1
else:
end = mid - 1
print(end)세번째 풀이(재귀)
재귀함수의 return 문으로 결과값을 반환하도록 하였다.
이것도 만약 mid 값이 조건을 만족하는 경우 mid+1 ~ end 의 범위에서도 조건을 만족하는지 확인하기 위해 재귀호출을 진행해준다.
k,n = map(int,input().split())
arr = [int(input()) for _ in range(k)]
start, end = 1, max(arr)
def binarySearch(start,end,n):
if start > end: return 0
mid = (start+end)//2
cnt = 0
for v in arr:
cnt += v//mid
if cnt >= n:
res = binarySearch(mid+1, end, n)
if res == 0: return mid
else: return res
elif cnt < n:
end = mid - 1
return binarySearch(start,end,n)
else:
start = mid + 1
return binarySearch(start,end,n)
print(binarySearch(start,end,n))