목록백준 (1)
이것저것
[백준] 1114번 - 통나무 자르기
이 문제는 이분탐색을 활용하는 문제다. 이분탐색을 통해 가장 긴 조각의 최소값을 찾을 수 있다. 1~L(통나무전체길이) 까지의 길이 중 검사할 길이를 이분탐색으로 정하고 통나무의 가장 긴 조각이 이보다 작은지 검사해서 가장 긴 조각의 최소값을 찾으면 된다. 그런데 통나무의 모든 조각이 특정 길이보다 작은지 검사할 수 있는 방법이 생각이 안났다. 그래서 아래 질문 글의 코드를 참고하여 그 방법을 알아보았다. https://www.acmicpc.net/board/view/51740 간단하게 말하면 그냥 한쪽끝에서 통나무조각이 검사하는 길이에 최대한 가깝게 자르면 된다. 처음에는 잘 이해가 안됐는데 생각보다 간단했다. 그림과 같이 길이가 L인 통나무가 있고 통나무의 모든 조각이 S보다 작은지 확인해보자 x <..
스터디/Algorithm
2022. 8. 2. 22:51