-
어떤 구간과 관련된 처리를 해야 할 때
일단 정렬부터 한 후 생각을 하자. -
예시
: 만약에 이러한 입력 순의 start ~ dest 값이 있따고 하고,
for문 돌려가면서 처리할 때 2번 이후에 3,4,5,6번의 사이값들을
지나칠 수 있음.
-> 하지만 시작점이나, 도착점을 잡고 정렬을 하게 되면 1~6번까지
모두 탐색이 가능함.
--> 시간 복잡도 감소시킬 수 있음.
정렬 시킨 타겟값.
반드시 시작점이 타겟이 아님.
문제를 보고 , 최적의 값이 나올 수 있는 타겟값을 찾아야 함.
- 힌트가 될수 있는 것은 : 반례임.
문제 : 가장 많은 횟수는?>
start를 기준으로 하면 1번이 선택되고 이때는 2개임.
but des를 기준으로 하면 2번이 선택되고, 이때는 3개임.
size를 기준으로 할 수 있음.
🔥🔥🔥