[BOJ 28353] 고양이 카페

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

28353번: 고양이 카페

 

- 문제 요약

 

찬우는 친구들과 고양이 카페에 가려 한다.

고양이 카페에는 N마리의 고양이가 있다.

i번째 고양이의 무게는 w_i이다.

찬우와 친구들은 모두 고양이를 사랑하기 때문에 무릎 위에 고양이를 정확히 2마리 데리고 있으면 행복해진다.

하지만 허약한 찬우와 친구들은 데리고 있는 두 고양이의 무게의 합이 K를 넘는다면 버티지 못할 것이다.

각 고양이의 무게와 한 명이 버틸 수 있는 최대 무게 K가 주어질 때 최대 몇 명이 행복해질 수 있는지 구해보자.

 

 

- 알고리즘 정리

 

고양이들을 오름차순으로 정렬해주고 고양이의 무게를 2개씩 짝지어서 합이 K 이하인 쌍의 최대 갯수를 구해주면 됩니다.

다양한 전략이 존재하기 때문에 그냥 그리디하게 풀어주면 됩니다.

 

 

- 코드 작성

 

#include <bits/stdc++.h>
using namespace std;

#define MAX 5001
int n,k,arr[MAX],r;

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	sort(arr+1,arr+n+1);
	for(int i=1,j=n;i<j;i++){
		while(i<j&&arr[i]+arr[j]>k){
			j--;
		}
		if(i<j&&arr[i]+arr[j]<=k){
			r++;
			j--;
		}
	}
	cout<<r;
}

코드 제출 결과