떡볶이 떡 만들기

1. 문제 설명

---

2. 문제 조건

---

3. 문제 해결 아이디어

• 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정
• 현재 이 높이로 자르면 조건을 만족할 수 있는가?를 확인한 후 탐색 범위를 좁히기
• 절단기의 높이는 0~10억까지 정수 중 하나
  • 큰 범위는 대부분 이진 탐색
• 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 나올 동안 중간점의 값을 기록한다.

 

[Step 1]

• 시작점: 0, 끝점: 19, 중간점: 9(자르고자 하는 높이)
• 이때 필요한 떡의 크기: M = 6이므로, 결과 저장
• 탐색 범위는 0~19이다 중간점은 나누면 9가 될 것이다.
• 잘린 떡의 길이는 모두 25가 나온다. 중간점의 9를 기록하고 중간점을 오른쪽으로 높이면서 또 확인한다.

 

[Step 2]

• 시작점: 10, 끝점: 19, 중간점: 14
• 필요한 떡의 길이가 M = 6이므로 (잘린 떡은 9) 결과 14를 기록하고 오른쪽으로 한칸 또 옮긴다.
• 시작점을 중간점보다 1큰걸로 위처럼 설정한다.

 

[Step 3]

• 이경우 만족하지 못하므로 결과를 저장하지 않는다.
• 다시 끝점을 중간점의 왼쪽인 16으로 바꾼다.

 

[Step 4]

• 시작점: 15, 끝점: 16, 중간점: 15
• 잘린 떡이 6이 맞으므로 현재의 중간점의 결과를 저장한다.
• 그리고 종료한다.

---

4. 소스코드

#떡의 개수(n)와 요청한 떡의 길이(m)을 입력
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)

• 매번 mid값을 설정하게 해주고 x(현재 떡이) mid보다 클 경우
• 높이를 줄이고 늘리는 과정을 반복한다.