99클럽 코테 스터디 18일차 TIL / 그리디

✏️ 문제

[백준/BOJ] 2212번: 센서(https://www.acmicpc.net/problem/2212)

 

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 G5

✅ 소요 시간: 권장 시간 안에 제출하긴 했지만 스스로 푼 게 아니기 때문에 의미 없음 

✅ 권장 시간: 1시간 30분

 

👩‍🏫 참고

- https://www.acmicpc.net/board/view/22142

- https://yuna0125.tistory.com/48

- https://aia1235.tistory.com/104

 

💡 풀이

1) 문제 이해

문제를 여러 번 읽었는데도 입출력 예시 이해가 안돼서 시작부터 쉽지 않았다. 백준 질문 게시판 뒤지다가 네임드 유저 한 분의 짧고 명확한 설명을 본 후에야 이해할 수 있었다.

 

입출력 예시 1

 

입출력 예시 1에서 주어진 집중국의 수는 2개고 [1, 3] 구간을 커버할 수 있는 집중국 하나, [6, 9] 구간을 커버할 수 있는 집중국 하나 이렇게 설치하면 전체 수신 가능영역 길이는 2([1, 3] 구간 길이)+3([6, 9] 구간 길이) 해서 5가 된다. 이것보다 수신 가능영역 길이를 더 줄일 수 있는 방법은 없다.

 

내가 문제 이해를 어려워한 이유는 '집중국의 정확한 위치를 찾으려고'해서 인 것 같았다. 집중국을 설치하는 위치가 중요한 게 아니라 주어진 좌표를 적절한 구역으로 나누는 게 중요한 건데 아예 핀트가 나갔었다는 생각이 든다.

 

2) 아이디어 흐름

자력으로 떠올린 아이디어가 아니라 다른 분들의 코드를 정리하면서 이해한 내용이다.

 

① 센서 좌표 정렬

좌표 값이라고 했기 때문에 당연히 정렬해서 써야겠다는 느낌이 들어서 이 과정은 바로 떠올릴 수 있었다.

 

② 인접한 센서 간 거리 차이 계산

딱 정렬까지만 떠올리고 정렬한 후 좌표들을 어떻게 활용할지 떠올리지 못했다. 이웃한 센서의 거리 차이를 계산하는 이유는 '센서를 몇 개의 그룹으로 나누고 각 그룹의 수신 가능 영역 길이 합을 최소화하기 위해 서로 인접한 센서들끼리 그룹을 이루는 게 가장 유리해서' 이다.

 

적다 보니 말이 좀 길어지긴 했지만 위 내용을 한 마디로 정리하자면 '가까이 있는 센서들끼리 묶어주는 게 가장 최적의 방법'이기 때문이다.

 

③  ⭐ K개의 그룹을 만들기 위해 거리 차이가 가장 큰 구간 K-1개 끊기 ⭐

이 부분이 문제 풀이의 핵심이라고 생각한다. 거리 차이가 큰 구간 K-1개를 끊는다는 의미에 대해 조금 더 자세하게 풀어서 써보겠다.

 

ⅰ)  경계?

- 센서 좌표가 [1, 3, 6, 7, 9]라고 할 때, 각 센서 사이의 거리 차이가 존재함

- 이웃한 센서 간 거리를 '경계'라고 한다면 [1과 3 사이의 거리, 3과 6 사이의 거리, 6과 7 사이의 거리, 7과 9 사이의 거리] 총 4개의 거리가 나옴

- 즉 센서 좌표가 N개면 경계의 개수는 N-1개

 

ⅱ) K개의 그룹을 만들기 위해 필요한 경계의 개수?

- 5개의 센서를 2개의 그룹으로 나누려면 경계 하나가 필요함

- 즉 만들고자 하는 그룹이 K개면 필요한 경계의 계수는 K-1개

 

ⅲ) 경계 끊기?

- 경계를 활용해 거리가 큰 순서대로 K-1개를 제외해주면 됨

- K=2, 센서 좌표가 [1, 3, 6, 7, 9]일 때 만들어지는 경계는 [2, 3, 1, 2] → 거리가 제일 큰 [3, 6] 구간에서 끊어주고 1, 3 / 6, 7, 9로 만들면 이 때의 영역 합이 최소

 

3) 구현

N = int(input())

K = int(input())

sensors = sorted(list(map(int, input().split())))

diff = []

for i in range(1, N):
    diff.append(sensors[i]-sensors[i-1])

diff.sort()

print(sum(diff[:N-K]))

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 문제를 이해하는 것

❗ 배운 점

1) 241114 항해99 그리디 알고리즘 특강 정리

• BFS/DFS, 이분탐색, ... 처럼 정해진 코드 형식이 없기 때문에 어려울 것
• 알고리즘 대신 방법론, 전략이라는 표현과 함께 쓰이기도 함
• 장점) 빠름, 매 순간 최적의 선택만 하기 때문에 메모리 효율적(굳이 모든 정보를 가지고 있지 않는 느낌으로 이해)
• 단점) 따져봐야 하는 조건이 많아지면 부적합
• 대표적인 그리디 유형: 최단경로(다익스트라), 최소 스패닝 트리 관련(크루스칼, 프림), 배낭 문제, 회의실 선택, 동전 문제
• ⭐ 대표 유형 문제를 제외한 이외의 문제는 '그리디 써서 풀어야지~'하면 오히려 더 어려워하는 경우를 많이 봄
• ⭐⭐ 가장 효율적인 방법이 뭘지 로직 고민한 다음 그대로 구현하고 '아 이게 그리디 풀이구나'를 깨달으면 됨

2) 생각 정리

• 특강 듣고 나니까 그리디와 좀 더 가까워진 느낌이다. 모든 문제를 유형화해서 접근하려는 이 딱딱한 사고 방식을 멈추자-!