떡볶이 떡 만들기(Python)

떡볶이 떡 만들기(Python)

 

 

문제 : 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단기에 높이(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이다.

출력 조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

문제 풀이

이 문제는 도저히 감이 안와서 짧은시간 고민후에 풀이를 찾아보았다. 

풀이에는 파라메트릭 서치라는 개념이 등장하는데, 이는 '최적화 문제를 결정 문제'로 바꾸어 해결하는 기법이다. 문제를 보고 '100만개의 떡이 주어지는데 이걸 하나하나 어떻게 넣지?' 생각을 했는데 풀이를 보니 아주 간단하게 구현이 되었다. 이 문제에서 파라메트릭 서치가 어떻게 사용되었는지 살펴보자.

 

절단기의 높이는 1부터 10억까지의 수이다. 이는 대단히 큰수라는 걸 알 수 있고, 우리는 절단기의 높이를 중점으로 문제를 풀어나가야 하기 때문에 이진 탐색을 떠올렸어야 한다. 순차탐색을 예시로 들어보면 최악의 경우에는 1부터 10억까지 10억번의 비교와 떡의 개수가 100만개 있기 때문에 말도 안되는 값이 나온다. 그렇기에 이 문제는 반드시 이진 탐색으로 풀어야만 한다.

 

이진 탐색이라면 높이가 10억까지의 경우에도 대략 31번만의 경우의 수를 모두 고려할 수 있다. (log10억을 생각해보면 알 수 있다.) 그 수에 떡의 개수가 100만개라고 해도 약 3000만 번 정도의 연산으로 해결이 가능하다. 

 

문제 해결

1. start와 end를 가장 긴 떡을 기준으로 정한다. (start=0, end=가장 긴떡의 길이)--->모든 경우를 만들 수 있다.

2. mid값으로 다 자른 뒤 남는 떡의 길이의 총합이 요구하는 떡의 길이보다 작다면 end를 mid-1로 주어 다시 start와 end를 통해 mid를 설정한다. 반대의 경우에는 start를 mid+1로 주면 된다.

3. 절단기 높이의 최대값을 구하는 것이기 때문에 떡의 길이가 같지 않아도 된다. 대신에 떡이 더 많거나 같아야한다. 때문에 떡이 남는 경우에는 result = mid를 먼저 주어야한다. 

 

소스 코드

n,m = map(int,input().split())
array = list(map(int, input().split()))


result = 0
start =0
end = max(array)

while (start <= end):
  mid = (start+end)//2
  total =0

  for i in array:
    if i > mid :
      total += i-mid
    
  if total < m :
    end = mid-1
  else :
    result = mid
    start = mid+1

print(result)

 

 

문제를 통해 알게 된 점

떡의 개별 높이는 array = list(map(int,input()))을 통해 바로 접근할 수 있다.
내가 했던 풀이 : 
box=0
for i in input().split():
  (box++) = i  -->파이썬에서 오류 ++연산이 되지 않는다.

문제의 핵심은 start가 end보다 크면 바로 반복문을 종료한다는 것이다.
이진탐색문제에 있어 이 개념이 이해가 되지 않는다면 숫자를 대입해 해보는 걸 추천한다.
그리고 반복문 내부에 else문에 total이 크거나 같다로 주는 것이 맞다. toal과 m이 같을 때 종료하는 건
당연하고, 차라리 total이 요구한 값보다 1이라도 더 큰것이 최대값이라고 볼 수 있기 때문이다.
이진탐색 코드는 상당히 중요한 개념이기 때문에 외워서 사용하는 것도 좋은 방법이다.