[ 백준 28353 ] 고양이 카페 (c/c++)

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

 

 

[ 문제 요약 ]

버틸 수 있는 무게의 최대값이 K일 때 고양이를 정확히 2마리 데리고 있으면 행복해진다. N마리의 고양이의 무게 주어질 때 행복해질 수 있는 사람의 수의 최대값을 출력한다.

 

 

[ 문제 풀이 ]

1. 우선 고양이의 무게 순으로 정렬을 한다.

2. 고양이 무게의 최대값과 최솟값을 더했을 때 K보다 아래라면 사람의 수를 1 늘리고 두 번째로 가벼운 고양이와 무거운 고양이의 합을 비교한다.

3. 만약 K보다 크다면 그 다음으로 무거운 고양이와 더했을 때 K보다 아래인지 비교한다.

4. 이렇게 비교를 하다가 무거운 고양이가 가벼운 고양이보다 가벼울 경우 종료한다.

 

 

[ 소스 코드 ]

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

int N, K, cnt = 0;
int arr[5050];

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

    int right = N-1, left = 0;
    while (right > left){
        if (arr[right] + arr[left] <= K){
            right--; left++;
            cnt++;
        }
        else right--;
    }
    cout << cnt;
    return 0;
}

 

 

 

[ 주의할 점 ]

두 포인터 기법을 사용하면 된다.