(JAVA) 백준 2212번 : 센서 --- [그리디]

www.acmicpc.net/problem/2212

2212번: 센서

 

안녕하세요.

 

그리디 알고리즘 문제입니다.

 

처음 문제를 읽었을 때, 문장이 어렵게 적혀있어서 이해하느라 애먹었네요..

 

 

백준에 해당 질문과 답을 보고 이해했습니다. 참고하실 분 참고하세요!

www.acmicpc.net/board/view/46572

글 읽기 - 문제 설명이 모호해서 헷갈립니다..

 

정리하자면,

 

 

입력 예제가 

 

6

2

1 6 9 3 6 7

 

이 있을 때,

집중국은 2개를 설치할 수 있습니다.

그럼, 1 3 6 6 7 9 좌표에 센서들이 있다면,

2좌표, 7좌표에 하나씩 설치하면 범위가 1, 2로 1+2 = 3 이 정답이 아니냐?

 

라고 헷갈렸습니다.

 

하지만, 이렇게 센서 사이 특정 좌표에 집중국을 설치하는게 아니라

센서를 집중국 개수만큼 집합하면 됩니다. 즉, 묶으면 됩니다.

[1, 3] 과 [6, 9] 로 묶으면 범위가 2 + 3 = 5 로 최소이고, 곧 정답입니다.

 

 

 

그럼, 바로 솔루션 들어가겠습니다.

솔루션

---

입력 예제가

 

6

2

1 6 9 3 6 7

 

이 있을 때.

 

 

  1)  센서 좌표 값 배열(Array가 List보다 더 빠름) 에 담기

    -> 집중국을 설치하기 위해 구역을 찾아야 합니다.

 

  2)  센서 좌표 값 배열 오름차순 정렬

    ->  1)과 일치

 

  3)  센서 사이 간격 값 구해서 오름차순 정렬

    ->  간격을 알아야, 최소합을 찾을 수 있습니다.

 

  4)  가장 높은 간격 값부터 K - 1(집중국 개수 - 1) 개를 전부 0으로 만듬

    ->  K - 1개를 0으로 만드는 이유는, 위 예시에서 [1, 3] 과 [6, 9] 두 구역을 나눴을 때, 3과 6 사이 간격은 고려하지 않습니다. 3과 6 사이가 3으로 모든 간격 값 중 가장 높은 값이었죠.

 

즉, 집중국을 놓을 때 두 센서를 하나의 구역에 포함시키지 않고 분리했으므로 두 센서 사이 간격은 무시됩니다. 이를 응용한다면, 가장 간격이 높은 값을 기준으로 분리시켜 구역을 만들면 최소합이 나오겠죠?

 

  5)  모든 간격 값 더하기

 

 

이 때, 4)와 5)를 하나의 for문으로 수행할 수 있습니다. 즉, 간격 배열을 오름차순 정렬헀을 때, index 0부터 시작해서 N - K개를 순환하면 됩니다!

 

 

 

 

이상입니다.

 

감사합니다!

 

*** 참고로, 소스코드에는 List와 Array 두 가지 방법의 해설이 있습니다. 채첨 결과, Array가 메모리 / 속도 측면에서 훨씬 우수했습니다!

소스코드

---