[문제]
오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다.
동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는
절단기로 잘라서 맞춰줍니다.
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고,
낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면
자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다.
손님은 6cm만큼의 길이를 가져갑니다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의
최댓값을 구하는 프로그램을 작성하세요.
[입력 조건]
1. 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어집니다. (1 <= N <= 1,000,000, 1 <= M <= 2,000,000,000)
2. 둘째 줄에는 떡의 개별 높이가 주어집니다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼
떡을 사갈 수 있습니다. 높이는 10억보다 작거나 같은 양의 정수 또는 0 입니다.
[출력 조건]
적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력합니다.
<입력 예시>
4 6
19 15 10 17
<출력 예시>
15
[풀이]
n, m = list(map(int, input().split()))
arr = list(map(int, input().split()))
start = 0
end = max(arr)
result = 0
while(start <= end) :
total = 0
mid = (start+end) // 2
for x in arr :
if x > mid :
total += x - mid
if total < m :
end = mid - 1
else :
result = mid
start = mid + 1
print(result)
먼저 떡의 개수(n)과 요청한 떡의 길이(m)을 입력받고 각 떡의 개별 높이 정보를 의미하는 arr 또한 입력받는다.
그리고 시작점(start)와 끝점(end)를 설정해주고 이진 탐색을 수행한다.
이진 탐색을 수행할 때는 반복문을 사용하며, 해당 범위를 반으로 나눠 변수 mid에 할당해 준 뒤
for문을 통해 떡을 잘랐을 때 떡의 양을 누적해가며 계산한다.
만약 떡의 양이 부족한 경우, 중간점을 기준으로 왼쪽 부분을 탐색하여 더 많이 자를 수 있도록 하고
만약 떡의 양이 충분한 경우, 중간점을 기준으로 오른쪽 부분을 탐색하여 덜 자를 수 있도록 한다.
또한, 최대한 덜 잘랐을 때가 정답이므로, else 내부에 변수 result 에 중간점 값을 할당해주고 최종적으로 해당 값을 출력한다.
출처
이것이 코딩 테스트다 with 파이썬 - 나동빈 저
'알고리즘 > 이코테 실전문제' 카테고리의 다른 글
[다이나믹 프로그래밍] 이코테 (파이썬) 개미 전사 풀이 (0) | 2021.08.30 |
---|---|
[이진 탐색] 이코테 (파이썬) 정렬된 배열에서 특정 수의 개수 구하기 풀이 (0) | 2021.08.27 |
[이진 탐색] 이코테 (파이썬) 부품 찾기 풀이 (2) | 2021.08.27 |
[정렬] 이코테 (파이썬) 두 배열의 원소 교체 풀이 (0) | 2021.08.25 |
[정렬] 이코테 (파이썬) 성적이 낮은 순서로 학생 출력하기 풀이 (0) | 2021.08.25 |