1. Problem 📃
📚 출처 - 1654-랜선자르기
문제 설명
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 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개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
입출력 예
| 예제 입력 | 예제 출력 | |
|---|---|---|
| 1 | 4 11 802 743 457 539 | 200 |
2. Logic 👨🏫
이 문제는 이분탐색 알고리즘을 사용하면 쉽게 해결이 가능하다.
- 임의의 중간값을 정하기 위해 list내의 가장 큰 값과 1로 정한 최솟값을 이용해 중간값을 정해준다.
- 중간값을 이용해 list의 값들을 나눠 lines의 총합을 구해준다.
- lines의 개수가 N을 넘는다면
start = mid + 1로, N을 넘지 못한다면end = mid - 1로 해준다.- 1, 2, 3의 과정을 반복해주면 반복문을 탈출하게 되고, end 값이 우리가 원하는 값인것을 알 수 있다.
3. Code 💻
1. 내가 푼 코드😁
K, N = map(int, input().split())
# K가 가지고 있는거
# N이 만들어야 될 개수
# 가지고 있는 K개의 길이 입력
list = [int(input()) for _ in range(K)]
start, end = 1, max(list)
while start <= end:
mid = (start + end) // 2
lines = 0
for i in list:
lines += i // mid
#print("lines: ", lines)
#print("start: ", start)
#print("end: ", end)
#print("mid: ", mid)
#print()
if lines >= N:
start = mid + 1
else:
end = mid - 1
print(end)4. Feedback 📚
1. 이분탐색 알고리즘 📕
데이터가 정렬 되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. 만약 X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을때까지 이 과정을 반복한다.
이진 탐색 예시
오름차순으로 정렬된 배열이 있다.
17, 28, 43, 67, 88, 92, 100
이 배열에서 이진 탐색을 사용해 43을 찾아보자
첫 번째 시도
우선 가운데 위치한 임의의 값 67을 선택한다.
선택한 값 67과 찾고자 하는 값 43을 비교한다.
43 < 67이므로 43은 67의 좌측에 존재한다는 것을 알 수 있다.
두 번째 시도
67을 기준으로 좌측에 있는 배열 값들을 대상으로 다시 탐색을 진행한다.
17, 28, 43
마찬가지로 가운데의 임의의 값 28을 선택한다.
28 < 43 이번에는 28이 43보다 작으므로 28 우측에 위치하는 것을 알 수 있다.
세 번째 시도
28의 우측을 기준으로 배열을 다시 설정해보면
43
배열에 값이 하나만 남게 되고 값을 확인해보면, 43 == 43 원하는 값을 찾았다.
종료 조건
탐색의 종료 조건은 원하는 값을 찾으면 종료된다.
운이 좋게 한 번에 찾을 수도 있고 위의 예제와 같이 마지막에 찾을 수도 있다.
만약 존재하지 않는 값을 찾게 되면, 최종적으로 배열이 남지 않게 되고, 그러므로 값이 존재하지 않는다는 것을 알 수 있다.
# 위의 과정은 수를 가지고 비교했고, 아래의 코드는 기본적인 이진탐색의 코드이다.
def BinarySearch(arr, val, low, high):
#해당 배열에 타겟 숫자 미존재
if low > high:
return False
#위치 기반으로 찾는 것
mid = (low + high) // 2
if arr[mid] > val: #수가 중앙 값보다 아래 있는 경우
return BinarySearch(arr, val, low, mid - 1)
elif arr[mid] < val: #수가 중앙 값보다 위에 있는 경우
return BinarySearch(arr, val, mid + 1, high)
else: #아니면 숫자를 출력
return True # -> return val