2212번
-
[백준 2212번] 센서(자바)Algorithm/Greedy Algorithm 2022. 3. 12. 16:54
백준알고리즘 2212번 : 센서 센서가 커버 가능한 수신 가능 영역을 잘 쪼개보니 실마리를 찾을 수 있었다. 센서의 위치를 정렬한뒤, 위치별 차이(즉 센서별 수신이 필요한 영역)를 새로운 배열로 정의한다. 새로운 배열(gap)의 값 중 큰 것부터 집중국의 개수-1 만큼 차감하여 합의 최솟값을 구한다. (집중국이 1개일때 차감없이 모든 영역을 커버할 수 있다.) 센서의 위치가 각 1 3 6 7 9 라고 한다면 각 센서의 차이는 2 3 1 2 이다. 집중국이 1개일때, 수신 가능 영역의 길이의 합은 2 + 3 + 1+ 2 = 8이다. 집중국이 2개일때, 수신 가능 영역의 길이의 합은 2 + 0 + 1+ 2 = 5이다. 집중국이 3개일때, 수신 가능 영역의 길이의 합은 2 + 0 + 1+ 0 = 3이다. 집중..