백준 휴게소세우기1 [알고리즘] 백준 1477 백준 1477이 문제를 처음 생각했을 때는 최대 힙을 사용하여 가장 큰 구간을 계속 선택하고, 이를 절반으로 나누면 되겠다고 판단했습니다. 하지만 반례를 확인하면서 구간을 절반으로만 나눌 수 있는 것이 아니라, 하나의 구간 사이에 3개 이상의 휴게소를 세울 수도 있겠구나라는 점을 깨달았습니다. 이를 인지한 후 다시 고민해봤습니다.처음에는 그리디 알고리즘으로 접근했지만, 앞선 휴게소 설치 개수가 뒤의 구간 길이에 영향을 주기 때문에 그리디로 해결할 수 없겠다는 결론을 내렸습니다. 그런데 문제의 입력 범위를 확인해 보니, 완전 탐색으로도 충분히 해결할 수 있을 것 같다는 생각이 들었습니다.알고리즘 문제를 풀 때 가장 먼저 해야 할 생각은 "이 문제를 완전 탐색으로 해결할 수 있을까?"입니다. 이 문제에서 구.. 2025. 2. 1. 이전 1 다음