[이코테] ch7. 이진탐색 실전문제3 떡볶이 떡 자르기 (백준 2805)

해당 문제는 백준 2805번 나무 자르기와 동일한 문제이나, 백준이 시간 제한이 1초로 더 짧다.

 

입력 가능한 값의 범위가 매우 커서 이진 탐색을 사용해서 가능한 경우를 찾아야겠다고 접근해야 한다.

다만, 여기에서 알고리즘에 매몰되는 실수를 했다.

 

내가 생각했던 방식은 떡의 길이를 입력받고 해당 리스트 안에서 이진탐색을 통해 중간값을 찾은 뒤, 잘라낸 길이의 총합을 target(m)과 비교하기였다. 이렇게 되면 입력받은 리스트 안에서 중간 값이지, 전체 길이의 평균이 아니다.... ㅠㅠ 사실 이 부분도 추가로 파고들면 어찌저찌 풀 수 있을 것 같기는 하다. 

 

---

잘못 접근한 방식 1. 재귀함수로 이분 탐색을 구현하고, 만약 엇갈린 경우 시작값과 끝값 사이에 가능한 경우가 있다고 생각하고 그 안에서 찾아봤다. 일단 파이썬은 시간 초과나고 pypy3는 틀렸다고 나온다. 게다가 아래 for문은 이진탐색한 의미가 없게 순차 탐색을 하고 있다.... ㅋ.T

# 잘못된 방향의 접근
import sys

input = sys.stdin.readline

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


def binary_search(array, target, start, end):
    if start > end:
        # array[start] ~ array[end] 사이에서 값 찾아야 함
        if array[start] <= array[end]:
            arr = [array[start], array[end]]
        else:
            arr = [array[end], array[start]]
        return arr
    mid = (start + end) // 2
    cutted = sum((i - array[mid]) if (i - array[mid]) >= 0 else 0 for i in array)

    if cutted == target:
        return array[mid]  # int형 return인 경우 바로 값 출력
    elif cutted > target:  # 너무 많이 자른 것. 더 긴 기준으로 다시 잘라보기
        return binary_search(array, target, mid + 1, end)
    else:  # 너무 적게 자른 것. 더 짧은 기준으로 다시 잘라보기
        return binary_search(array, target, start, mid - 1)


result = binary_search(data, m, 0, n - 1)

if type(result) == int:
    answer = result
else:  # 리스트가 돌아온 경우
    answer = 0
    for i in range(result[0], result[1]):
        cutted = sum((j - i) if (j-i) >= 0 else 0 for j in data)
        answer = i
        if cutted == m:
            break
        elif cutted < m:  # 작아지면 더이상 볼 필요가 없음
            answer = i + 1
            break

print(answer)

 

---

제대로 푼 풀이. 재귀 함수는 과하게 복잡해지는 경우라서 반복문으로 다들 많이 풀더라. 나도 그렇게 풀었다.

이렇게만 하면 원래 풀었던 방식의 불필요한 방식(그래프 안에서만 값을 찾으려 하고, 못 찾은 경우 범위를 리턴해서 그 범위 안에서 for문을 통해 값을 찾음)이 아예 사라지고 깔끔하게 이진탐색으로 풀 수 있다.

 

Python3 기준으로 백준 2803 통과했다. 

import sys

input = sys.stdin.readline

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

start = 0
end = max(data)

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

    cutted = sum((i - mid) if (i - mid) >= 0 else 0 for i in data)

    if cutted == m:
        answer = mid
        break
    elif cutted < m:  # 적게 잘라서 더 많이 잘라야 함 (왼쪽 부분 탐색)
        end = mid - 1
    else:  # 너무 많이 자른 것. 더 적게 잘라야 하므로 오른쪽에서 보기
        answer = mid  # 이 경우에는 답이 될 수도 있으니까 저장
        start = mid + 1

print(answer)

 

위 아래로 시간초과, 틀렸습니다의 향연이 펼쳐졌었다...