취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28353번 문제인 고양이 카페이다.
문제는 아래 링크를 확인하자.

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

먼저 고양이들을 무게를 기준으로 정렬하자. 그리고 무거운 고양이부터 한 마리씩 살피면서, 해당 고양이와 현재 남아있는 가장 가벼운 고양이가 무게의 합이 K 이하가 되는 짝을 이룰 수 있다면 새 짝을 하나 이루고 그렇지 않다면 해당 고양이를 제외하는 작업을 반복하는 그리디 전략으로 문제를 해결할 수 있다.

위의 전략이 올바른 답을 항상 찾을 수 있는 이유를 생각해보자. 만약 X개의 고양이 쌍을 구성할 수 있다면 각 쌍을 구성하는 두 고양이 중 가벼운 고양이를 선택되지 않은 더 가벼운 고양이로 바꾸는 작업을 반복하는 것으로 가장 가벼운 X마리의 고양이가 서로 다른 쌍에 들어있는 고양이 쌍 구성을 찾을 수 있음을 관찰하자. 따라서 X개의 고양이 쌍을 구성할 수 있다면 가장 가벼운 고양이 X마리들이 서로 다른 쌍에 들어가게 할 수 있어야 한다. 이 때 최대한 많은 고양이 쌍을 만들기 위해서는 가벼운 고양이일수록 더 무거운 고양이와 쌍을 구성하게 해야 함은 쉽게 관찰할 수 있다. 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, K;
int L, R;
int arr[5000];

int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];

	sort(arr, arr + N);

	R = N - 1;
	while (L < R) {
		if (arr[L] + arr[R] > K)R--;
		else ans++, L++, R--;
	}

	cout << ans;
}