[알고리즘/문제풀이][BOJ 2805번] 나무 자르기

나무 자르기 문제는 최적화 문제를 결정 문제로 변환하여 푸는 기법을 통해 해결할 수 있는 문제입니다. 적어도 ~이상의 나무를 가져가기 위해 전기톱을 최대한으로 설정할 수 있는 높이를 구하는 최적화 문제를 참, 거짓의 결정 문제로 변환하여 이분법으로 빠르게 해결할 수 있습니다. 최대의 값을 구하기를 결정 문제로 변환하면 "나무를 어떠한 값 이하로 잘랐을 때 적어도 ~만큼 가져갈 수 있는가?"라는 질문을 할 수 있습니다. 이 질문에 대해 참, 거짓으로 답을 하게 되면 그 값을 기준으로 이하나 이상에 대해서는 더 이상 질문을 할 필요가 없어지게 됩니다. 이분법의 논리와 같다는 사실에서 이분법을 그대로 적용하여 결국에는 최적의 값을 찾을 수 있게 됩니다. 작성한 코드는 다음과 같습니다. #include #pra..
알고리즘/문제풀이 2021. 9. 21. 22:36
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
반응형
250x250