❓문제
[실버2]
https://www.acmicpc.net/problem/2805 와 같은 문제이다.
오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기의 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 이걸 처리 안 해줘서 시간을 허비했다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1<=N<=1,000,000, 1<=M<=2,000,000,000)
- 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.
입력 예시
4 6
19 15 10 17
출력 예시
15
💭 아이디어
이 문제는 원하는 조건을 만족하는 가장 알맞는 값을 찾는 문제이다.
따라서 파라메트릭 서치를 사용하면 된다.
범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제의 경우 이진 탐색을 통해 결정 문제를 해결하며 범위를 좁힐 수 있다.
파라메트릭 서치 : 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
결정문제 : '예' 혹은 '아니오'로 답하는 문제
최적화 문제 : 목적함수(objective function)의 함수값을 최적화(최대화 또는 최소화)시키는 파라미터(변수) 조합을 찾는 문제
적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것이 포인트이다.
현재의 높이 h로 자르면 조건을 만족할 수 있는가 에 대해 예, 아니오를 확인한 후 탐색 범위를 좁혀서 해결한다.
이진 탐색을 떠올릴 수 있는 힌트는 문제에 숨어있다.
절단기의 높이(탐색 범위)가 1부터 10억까지의 정수 중 하나로 매우 큰 숫자이다. 이런 큰 수를 보면 이진 탐색을 떠올려야 한다.
만약 순차 탐색을 사용할 경우 시간 초과를 받을 것이다.
[시간복잡도에 대한 이해 ..]
이진 탐색으로 h를 찾는다면, 대략 31번만에 경우의 수를 고려할 수 있다. 이때 떡의 개수 N이 최대 100만개 이므로 이진 탐색으로 절단기의 높이 h를 바꾸면서 바꿀 때마다 모든 떡을 체크하는 경우 대략 최대 3,000만번의 연산으로 문제를 풀 수 있다.
문제의 시간 제한은 2초이므로 최악의 경우 3,000만번 정도의 연산이 필요하다면 아슬아슬하게 시간초과를 받지 않고 정답 판정을 받을 수 있다.
파이썬은 1초에 2,000만번 연산이 가능하다.
따라서 시간제한이 1초, n = 10만이라고 할 때 O(N^2)으로 짜게 되면 100억번의 연산이 필요하므로 시간초과가 난다.
이 경우, O(NlogN)으로 알고리즘을 짜야 1,600,000번의 연산으로 수행 가능하다.
❗ 풀이
정답
n, m = 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 # 최대한 덜 잘랐을 때가 정답이므로 일단 result에 기록
start = mid + 1
print(result)과정 해설
1. 시작점 0, 끝점 19(가장 긴 떡의 길이) - 중간점 9
-> 떡의 합 25, 필요한 떡의 길이인 6보다 크므로 result = 9, 오른쪽 탐색(시작점 증가)
-
시작점 10, 끝점 19, 중간점 14
-> 떡의 합 9, 필요한 떡의 길이인 6보다 크므로 result = 14, 오른쪽 탐색(시작점 증가) -
시작점 15, 끝점 19, 중간점 17
-> 떡의 합 2, 필요한 떡의 길이인 6보다 작으므로 왼쪽 탐색(끝점 감소) -
시작점 15, 끝점 16, 중간점 15
-> 떡의 합 6, 필요한 떡의 길이인 6과 동일하므로 result = 15 -
while문에 걸리므로 종료
이진 탐색 과정을 반복하며 중간점의 값은 시간이 지날수록 최적화된 값을 찾는다.
이하 코드는 이중 반복문을 사용한 .. 시간초과에 걸릴 나의 쓰레기 코드이다.
greedy하게 해결되지 않을까 했는데 어림없다!
n, m = map(int, input().split())
array = list(map(int, input().split()))
height = max(array) - m
max_height = 0
for h in range(height, max(array)):
sum = 0
for i in range(n):
if array[i] - h > 0:
sum += array[i] - h
if sum >= m:
max_height = h
continue
else:
break
print(max_height)✅ Comment
탐색 범위를 먼저 살피고, 범위가 매우 넓으면 이진 탐색을 떠올리자.
범위 내에서 조건을 만족하는 가장 큰 값을 찾는 최적화 문제는 이진 탐색으로 결정 문제를 해결하며 범위를 좁힐 수 있다!
➕ 재풀이
이하는 백준에서 재풀이한 내 답안이다.
def binary_search(array, height, start, end):
result = 0
while start <= end:
mid = (start + end) // 2
sum = 0
for k in array:
if k > mid:
sum += k - mid
if sum < height:
end = mid - 1
else:
result = mid
start = mid + 1
return result
n, m = map(int, input().split())
a = list(map(int, input().split()))
print(binary_search(a, m, 0, max(a)))-
떡 만들기와 같은 문제임을 직감하였으나 왜 이분탐색을 사용해야 하는지 근거를 찾으려 했다.
집으로 가져가려는 나무의 길이가 1~20억까지로 범위가 매우 넓었으므로 시간 제한이 1초일 때 시간 내 풀기 위해선 이분탐색을 이용해야 한다고 생각하였다. -
백준문제로 다시 풀이할 때 UnboundLocalError가 발생하였는데, 이는 정답 풀이에서 result = 0을 해주지 않았기 때문이었다. while 반복문 안에서만 result를 쓰다가, while문 밖에서(return result) result를 쓰니 에러가 뜬 것이다. 따라서 while문 밖에서 result 변수를 선언해주었다.
-
처음 탐색할 때 시작점은 0이다.
다시 풀이할 때 min(array)이지 않을까 하였는데 아니나 다를까 오답이었다!
-> 예를 들어 나무의 높이가 다 다르다고 하는 조건도 없어 만약 나무의 높이가 9 9 9 9로 모두 같은 경우 시작점이 9가 되면 안될 것이다.
