(백준 2212번 센서 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 4탄

아침에 문제만 읽고 점심시간에 골똘히 풀이를 생각해본 문제! 생각보다 아이디어가 금방 나와서 신기했다ㅎㅎ

 

이전 발행글은 여기↓

2024.01.02 - [알고리즘] - (백준 11047번 동전 0 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 3탄

(백준 11047번 동전 0 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm)

 

백준 2212번

https://www.acmicpc.net/problem/2212

2212번: 센서

 

풀이과정

 

우선 문제에서 나온 예제를 생각해보자. 예제에서는 N=6, K = 2인 경우를 고려했다.

각각의 센서 위치를 Arrr에 넣어서 생각하자.

(Arr은 이미 정렬이 되어 있다고 가정하자. 문제에서는 정렬이 안 되어있지만 sort함수를 사용하면 쉽게 정렬할 수 있다!)

그리고 각각의 센서의 거리를 Dis 배열에 넣어보자.

각 집중국의 수신가능영역 거리의 합이 최소가 되기 위해서는 거리가 먼 센서들이 있는 부분에 먼저 집중국을 배치해주어야 한다.즉, x = 3과 6부분에 집중국을 배치해주면 답 5가 나온다.

 

 

이걸 Dis 배열을 이용해서 생각해보면 Dis 배열에서 가장 큰 수인 3을 제외한 나머지 합이 정답이 됨을 알 수 있다. 

첫번째 예제

같은 방법으로 두번째 예제는 다음과 같이 풀 수 있다.

오오.. 규칙성이 조금씩 보인다...!!!🤭

이걸 코드로 짜면 아래와 같다. 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>

int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	int* Arr = new int[N];
	int* Dis = new int[N - 1];
	for (int i = 0; i < N; i++) scanf("%d", &Arr[i]);	
	std::sort(Arr, Arr + N);
	
	for (int i = 0; i < N - 1; i++) Dis[i] = Arr[i + 1] - Arr[i];
	std::sort(Dis, Dis + N - 1);
	
	int sum = 0; 
	int cnt = 0; 

	while (1) {
		if (cnt == N - K or N-K <=0) break;
		sum += Dis[cnt];
		cnt++;
	}

	printf("%d", sum);

	delete[] Arr;
	delete[] Dis;
	return 0;
}

 

그런데 런타임 에러가 났따..

런타임 에러가 난 이유는... 생각지도 못한 곳이 문제였다!

문제에서 N개의 센서와 K개의 집중국을 세울 때 N와 K의 범위만 제시했을 뿐, 이 두 숫자의 관계는 제시하지 않았다.

놀랍게도 N개의 센서보다 K개의 집중국이 더 많은 경우도 고려해주어야 한다!!

 

즉, N > K인 경우를 고려해줘야 한다!! 이때 당연히 답이 0이 된다.

 

나는 while 문 안에서 Dis[cnt]를 부를 때 cnt의 범위를 N-K보다 작을 때만 고려해주었는데, N-K<0인 경우에 대해서도 작성했어야 했따!!!

 

이렇게 또 배운다...🤭🎵