프로그래머스 (징검다리) with python

이 문제의 경우 먼저는 제한사항을 보고 도착지점까지의 거리 distance가 10억 이하라는 것을 보고 이분탐색으로 풀어야한다는 것을 유추해내는 것이 좋다. 그러나 이후 문제에서 이분탐색을 어떻게 써야할 지가 너무나 막막하다 처음에는 combination을 통해 바위의 위치를 두 개 선택하여 제거하고 난 뒤 이분탐색을 쓰려고 시도했으나 이는 시간복잡도에서 문제가 발생하여 다른 방법을 고안하였다. 바위의 위치를 굳이 알아내어 제거하지 않더라도 제거할 바위의 개수를 변수로 두고 해당 변수와 n값을 비교하고 이를 이분탐색에 반영하게 되면 문제를 풀 수 있다는 것을 생각해냈다. 이 코드를 보게 되면 우선 left,right는 distance까지의 범위로 설정해두고, 이에 대한 mid값을 거리의 최솟값으로 두고 ..

2021.02.23