문제
절단기에 높이를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 그렇게 높이보다 많이 잘린 떡을 손님이 가져간다. 손님이 길이가 M인 떡을 요청했을 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오
입력 조건
1. 첫째 줄에 떡의 개수 n과 떡의 길이 m이 주어진다.
2. 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 m 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다.
출력 조건
1. 적어도 m만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
내 코드
#1 탐색을 이용한 풀이
n,m = list(map(int,input().split()))
# Q1. 떡 n개의 개수를 입력해주어야 하는데, 반복문을 통해 입력받아야되나?
# Syntax적인 부분 -> 어떻게 보면 구현
array = list(map(int,input().split()))
cut_height = max(array)
# 탐색
while(True):
dduck = 0
for i in range(len(array)):
temp = array[i] - cut_height
if (temp > 0):
dduck += temp
if dduck == m :
print(cut_height)
break;
else:
cut_height-=1해설
#1. 일단은 문제의 해결에 초점을 두었다. 따라서 순차 탐색을 이용하였고, 절단기의 높이 (cut_height)의 초기값을 제일 긴 떡의 길이로 설정하고 정수 1씩 줄여나가는 방법을 이용하였다.
교재 코드
n,m = list(map(int,input().split()))
array = list(map(int,input().split()))
start=0
end = max(array)
result = 0
while(start<=end):
total = 0
mid = (start + end) //2
for x in array:
if x>mid:
total += x-mid
if(total < m):
#왼쪽 영역으로
end = mid-1
else:
#오른쪽 영역으로
result = mid
start = mid+1
print(result)교재해설
전형적인 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제이다. 파라메트릭 서치라 함은 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.
본 문제의 풀이 아이디어는 의외로 간단한데, 적절한 높이를 찾을 때까지 절단기의 높이를 반복해서 조정하는 것이다. 이를 바탕으로 조건의 만족 여부에 따라 탐색 범위를 좁혀서 해결할 수 있다.
절단기의 높이(=탐색범위)는 10억까지의 정수인데, 이와 같이 큰 수의 범위가 주어진다면 가장 효율적인 이진 탐색을 이용하는 것이 옳다.
10억이라는 큰 수라도 이진 탐색을 이용한다면 31번만에 경우의 수를 모두 고려할 수 있다.
참고
이것이 코딩테스트다 with Python (나동빈 저)
