[PART2] 7-2(이진 탐색): 떡볶이 떡 만들기

코뉴·2021년 2월 1일

이진탐색 이코테

이코테: 문제풀이

목록 보기

22/28

💥이코테 실전문제 뽀개기💥

💻 7-2 떡볶이 떡 만들기

난이도🖤🖤🖤🤍🤍🤍 | 풀이시간 40분 | 제한시간 2초 | 메모리제한 128MB

📌2021/02/01 작성 코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
forest = list(map(int, sys.stdin.readline().rstrip().split()))

# 절단기 설정 높이 h를 기준으로 이분 탐색 실행
start = 0
end = max(forest)
answer = 0
while start <= end:
    h = (start + end) // 2
    cutting = 0
    # 현재 h로 자를 수 있는 길이 구하기
    for tree in forest:
        if tree > h:
            cutting += (tree - h)
    if cutting >= m:
        # 일단 answer에 저장
        answer = h
        # h 늘려보기 (잘리는 길이 적게)
        start = h + 1
    elif cutting < m:
        # h 줄여보기 (잘리는 길이 많게)
        end = h - 1
print(answer)

🔴 백준 2805 나무자르기 문제와 완전히 같은 문제
-> 백준 2805의 코드를 복사해 넣었음.

💭 아이디어

https://velog.io/@eastgloss0330/%EB%B0%B1%EC%A4%80-2805-%EB%82%98%EB%AC%B4-%EC%9E%90%EB%A5%B4%EA%B8%B0

🤓 문제 해설 (이진 탐색)

전형적인 이진 탐색 문제이자, 파라메트릭 서치Parametric Search 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 결정 문제(Y/N로 답하는 문제)로 바꾸어 해결하는 기법이다.
'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. 코딩 테스트나 프로그래밍 대회에서는 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.

이 문제의 풀이 아이디어는 의외로 간단한데 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것이다. 그래서 '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부에 따라서 탐색 범위를 좁혀 해결한다. 범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀 나간다.

절단기의 높이(탐색 범위)는 1~10억까지의 정수 중 하나인데, 이처럼 큰 수를 보면 가장 먼저 이진 탐색을 떠올려야 한다. 이 문제에서 절단기의 높이 범위가 한정적이었다면 순차 탐색으로도 해결할 수 있지만, 현재 문제에서 절단기의 높이는 최대 10억까지의 정수이므로 순차 탐색은 분명 시간 초과를 받을 것이다.

반면에 높이 h를 이진 탐색으로 찾는다면, 대략 31번 만에 경우의 수를 모두 고려할 수 있다. 아때 떡의 개수 N이 최대 100만개이므로 이진 탐색으로 절단기의 높이 H를 바꾸면서, 바꿀 때마다 모든 떡을 체크하는 경우 대략 최대 3,000만번 정도의 연산으로 문제를 풀 수 있다.

문제의 제한 시간은 2초이므로 최악의 경우 3,000만 번 정도의 연산이 필요하다면 아슬아슬하게 시간 초과를 받지 않고 정답 판정을 받을 것이다. 그렇다면 구체적으로 어떻게 이 문제를 이진 탐색으로 해결할 수 있을까? 절단기의 적절한 높이 H를 정하는 과정을 살펴보자.

1) 시작점은 0, 끝점은 가장 긴 떡의 길이로 설정. 중간점을 절단기 h로 설정.
2) 필요한 떡의 길이가 크면 시작점을 증가시킨다.
3) 필요한 떡의 길이보다 작으면 끝점을 감소시킨다.

중간점의 값은 시간이 지날수록 최적화된 값을 찾기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이의 합이 필요한 떡의 길이보다 크거나 같을 때마다 결괏값을 중간점(mid)의 값으로 갱신한다.

🤓 답안 예시 (이진 탐색)

# 떡의 개수(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 # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1

# 정답 출력
print(result)