[BOJ/백준 - 2805] 나무 자르기

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

2805번: 나무 자르기

---

---

주의 : 이분 탐색 아님!!! 개느림!!! (2160ms)

나는 거의 그리디? 완전탐색? 잘모르겠네.. 여튼 그런식으로 풀었음

푸는 방식은 입력을 받고 내림차순으로 정렬한다. (소스 보면 알겠지만 맨 뒤에 0이 더 있음)

 

앞에서부터 다음 원소의 높이와 같아지게 자르고 여태까지 잘랐던 나무를 더한다

그리고 그 값이 목표치와 비교해서

1. 딱 맞다면 다음 원소의 높이와 같다면 다음원소의 높이까지만 자르면되고

2. 아직 모자르다면 반복문의 다음 루프로 보낸다

3. 더 많이 잘랐거나 마지막 0과 비교할 때는

   다음원소의 값과 덜 자를만큼의 길이를 비교해서 계산한다

 

백준 input으로 예시를 들면

예시 1

4 7
20 15 10 17

정렬
20 17 15 10

계산 (실제 배열의 값은 변하지 않음)
나무의 길이    자른나무 길이의 합 :
20 17 15 10 
17 17 15 10 >  0 + (3*1) = 3  
15 15 15 10 >  3 + (2*2) = 7

예시 2

5 20
4 42 40 26 46

정렬
46 42 40 26 4

계산 (실제 배열의 값은 변하지 않음)
나무의 길이      자른나무 길이의 합
46 42 40 26 4  
42 42 40 26 4 >  0 + (4*1) = 4  
40 40 40 26 4 >  4 + (2*2) = 8
26 26 26 26 4 >  8 + (14*3) = 50

지금 30만큼 넘치게 잘랐다 
현재까지 나무는 3개를 잘랐으니 10만큼씩 덜 자르면 된다
그래서 26 + 10 = 36

이런 방식으로 자르고 특이케이스 부분들만 처리해주면된다 

5 2000000000 
900000000 900000000 900000000 900000000 900000000

이런 경우 값이 다 똑같기 때문에 마지막 원소까지 가게되었을 경우 절대값 처리를 해서 계산했다

 

일단 통과는 했는데 이분탐색으로 다시 생각하고 풀어봐야겠다