[백준 파이썬] # 2805 나무 자르기

Silver III

# 2805 나무 자르기

링크 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

풀이

N, M = map(int, input().split())
woods = list(map(int, input().split()))

S = 0
E = max(woods)
result = 0

def bs(arr, target, start, end):
    while start <= end:
        total = 0
        mid = (start+end)//2

        for i in woods:
            if i > mid:
                total += i-mid

        if total < M:
            end = mid - 1
        else:
            start = mid + 1
            result = mid

    return result

print(bs(woods, M, S, E))

 

후기

• 기본적인 풀이 과정은 나동빈님의 자료구조 강의 예제를 참고하였다. 흉내내는 것 까지는 하겠는데 아직 이해안되는 부분이 있다.
  cf. 떡볶이 떡 만들기
  Q. total == M, total > M, total <M으로 케이스를 구분할 때 오답처리, 반면 total >= M, total < M으로 구분할 때는 정답 → 원인에 대해 이해할 필요

• 풀이과정을 이해했다고 해서 안심해서는 안된다. 시간초과 문제가 발생하기 때문이다.

• 연산과정에서 전역변수와 지역변수 차이로 인해 사용자 함수를 정의해서 풀어야 시간초과 문제를 방지할 수 있다.
  아래링크는 이전 문제 중 동일한 상황이 발생했던 문제이므로 참고  

2022.02.22 - [Algorithm Study/Python] - [백준 파이썬] # 1929 소수 구하기 (복습 필요)

 

• 이진탐색.. 아직 너무 어렵다. 혈을 뚫어야 할게 너무 많아.. 그렇지만 비전공자라서 이해하기 어려운 추상적인 과정을 하나하나 알아갈 때마다 쾌감이 있다. 그 전까진 머리 싸매고 있지만.. ㅎㅎ

 

 

 

12:30 부터 떡볶이 떡 만들기 설명

https://youtu.be/94RC-DsGMLo?t=750