그룹짓기 문제.
못품 : 첫번째 생각.
1번. 아이디어.
-
일단 첫번째와 두번째 사이가 크면 어떻게 될까??? 를 생각해봄.
-> 그 다음 어떻게 하냐.... 음... 하다가 어지러웠다.. ㅋㅋ
-
1번. 정렬부터 하고
-
2번. 정렬된 상태에서 diff값을 구했다.
-
3번. 그 다음 어떻게 할까???? 기지국 선택은 최대 k번까지 가능하다...
2번 아이디어.
- 일단은 diff가 길면 굳이 해당 위치에다가 설치할 필요는 없다.( 그냥 거기다가 설치하고 해당 기지국 0으로 하면 됨.)
- -> 그건 그렇고 음. 그럼 k개는 뭔 관련이냐... 킁..
회고 1번.
- 2번 아이디어를 보면, 지금의 경우는 dist를 x값 이하로 하면서 진행한 것이다.
-> 그런데 이런식으로 하면 문제가 뭐냐면 n의 개수가 1만개이고, 그리고 dist를 줄여나가면서 해야 하므로 완전 탐색 이라 할 수 있다.
=> 왜냐하면 모든 배열의 값을 전부 확인하면서 진행하겠다는 것이고, 그 가운데 도대체 dist 값을 어떻게 선정할지도 알 수 없기 때문이다.
회고 2번
-
1번 아이디어처럼 접근하는게 맞았는데, 솔직히 확신이 들지 않았따.
-
그 다음에 내가 생각한 거는 연속적인 diff 인데 , 이거를 어떻게 할까?? 를 생가함.
구글링 물어봄
- 내가 왜 그다음 생각 못했을까?
참고 사이트 : 엥...
🔥🔥🔥