[Python][백준] 2805. 나무 자르기/ 이진탐색 (S2)

🔗링크 :  

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

 

---

🗒️파이썬 코드 풀이

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

start, end = 1, max(lst)
cnt = 0 

while start <= end : 
    cnt = 0 
    mid = (start + end) // 2
    for ls in lst : 
        if ls > mid : 
            cnt += (ls-mid)
    
    if cnt >= M : 
        start = mid + 1 
    elif cnt < M : 
        end = mid - 1 

print(end)

 

1. 이진탐색으로 문제를 해결하면 된다. 

 

2. 이진탐색에서 start point와 end point를 만들어준다.

 

3. start와 end의 중간 값을 mid 값으로 주고, 

전체 리스트 반복문으로 mid 보다 큰 값을 필터링하여 더해준다. 

(cnt가 필터링하여 더해준 값)

 

4. 필터링해서 더해진 cnt를 기준 높이인 M과 비교하여,

start와 end 값을 적절하게 변경해준다. 

 

 

✨ 내 문제 풀이

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

mx = max(lst)
cnt = lst.count(mx)
rs = tree = 0 
while tree < M :
    tree = tree + cnt 
    rs += 1 
    mx -= 1 
    if mx in lst :
        cnt += 1

print(max(lst) - rs)

 

해당 코드는 시간초과가 뜬 코드이다. 

얼핏 보면 더 간단해 보이고,

시간 복잡도 측면에서 이득일거라 생각했다.

 

실제로 시간 복잡도를 계산해보면 

해당 코드는 n^2이 되어서  최악의 경우 1,000,000 ^2이 된다. 

 

하지만 이진 탐색으로 문제를 풀 경우  Big O가 nlogn이 되어 1,000,000 log 1,000,000 이되고,   대략 6,000,000의 값이 된다

 

시간 복잡도 측면에서 이진탐색이 훨씬 훨씬 이득이 되는것이다. 

 

📌  문제 코멘트

경험이 있다면 쉽고, 경험이 없다면 좀 난이도가 있는 문제 같다. 

실제 구현 로직 자체는 어렵지 않은데, 

시간 복잡도를 고려하면 좀 생각을 해야하는 것 같다. 

 

특히 이진탐색이라는 것을 생각해야하는데, 아직 이진탐색 문제가 나에게는 덜 익숙한 것 같다. 

 

이번 문제를 통해 해당 문제의 시간 복잡도를 유심히 잘 봐보자 ! 

---

📚문제

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

 

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

 

예제 입력 1 복사

4 7
20 15 10 17

예제 출력 1 복사

15

예제 입력 2 복사

5 20
4 42 40 26 46

예제 출력 2 복사

36