[BOJ/CPP] 고양이 카페 - 28353번 / C++ 풀이

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

28353번: 고양이 카페

 

N마리의 고양이 중 2마리 몸무게의 합이 K 이하가 되는 최대 경우의 수

 

투포인터로 풀었다.

 

1. 배열 정렬

2. if(최솟값 + 최댓값 <= K)

-> true : cnt 1개 증가, 최솟값 포인터 +1, 최댓값 포인터 -1 (중복이 없어야함)

-> false : 최댓값 포인터 -1 . 왜냐하면 가장 가벼운 고양이 + 가장 무거운 고양이의 합이 K보다 크기 때문에 고양이의 무게를 줄여야 함!

최솟값 포인터가 최댓값 포인터보다 작을 때까지 실행하면 끝

 

 

전체 코드

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

int main() {
	int n, k; cin >> n >> k;
	vector <int> vc(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> vc[i];
	}
    // 오름차순 정렬
	sort(vc.begin(), vc.end());

	int start = 0, end = n - 1;
	int ans = 0;
	while (start < end) {
		int sum = vc[start] + vc[end];
        
        // 두마리의 고양이를 합친 무게가 k 이하라면 카운트 증가
		if (sum <= k) {
			ans++;
			start++; end--;
			continue;
		}
		// k보다 크다면 무게를 줄여야함! (무거운 고양이는 ㄲㅈ!)
		if (sum > k) {
			end--;
		}
	}

	cout << ans;
}

 

 

나는 예전에 너구리 카페 갔다가 난폭한 너구리한테 눈알 뽑힐뻔 ㅠㅠ