[백준] 28353번 고양이 카페 - C++

🌱문제 설명

28353번 고양이 카페

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

고양이 카페에는 N마리의 고양이가 있다. i번째 고양이의 무게는 w_i이다. 찬우와 친구들은 모두 고양이를 사랑하기 때문에 무릎 위에 고양이를 정확히 2마리 데리고 있으면 행복해진다. 하지만 허약한 찬우와 친구들은 데리고 있는 두 고양이의 무게의 합이 K를 넘는다면 버티지 못할 것이다.

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

---

입력

---

출력

행복해질 수 있는 사람의 수의 최댓값을 출력한다.

풀이

#include <iostream>
#include <algorithm> 
// sort 함수를 사용하기 위한 헤더
using namespace std;

int main() {
    int cat, K; 
    cin >> cat >> K;

    int arr[cat]; // 고양이 무게 배열 입력
    for (int i = 0; i < cat; i++) {
        cin >> arr[i];
    }

    // 무게 오름차순 정렬
    sort(arr, arr + cat);
		//투 포인터
		int left = 0;
    int right = cat - 1;
    int count = 0;

    while (left < right) {
        if (arr[left] + arr[right] <= K) {
            left++;
            right--;  // right를 감소
            count++;
        } else {
            right--;  // 합이 K를 넘으면 right만 감소
        }
    }
    cout << count << endl;
    return 0;
}

❣️문제 요약:

고양이 수, 버틸 수 있는 무게, 고양이들의 무게 배열을 입력받아서 버틸 수 있는 무게를 넘지 않도록 한 사람당 2마리의 고양이를 안도록 해서 2마리의 고양이를 가진 사람의 수를 구한다.

🤔 생각해야 할 점

1. 한 사람당 2마리의 고양이를 안을 수 있다.
2. 무게 k를 넘어서는 안된다.

→ 고양이 무게 배열을 만들어서 무게를 오름차순으로 정렬한 후 배열에서 2개를 뽑아 k를 넘지 않는 경우의 수를 센다.

→ 투 포인터를 이용해서 배열 검사

코드 설명

✅ 고양이 수, 버틸수 있는 무게, 고양이 무게 배열 입력 받기

    int cat, K; 
    cin >> cat >> K;

    int arr[cat]; // 고양이 무게 배열 입력
    for (int i = 0; i < cat; i++) {
        cin >> arr[i];
    }

✅ 고양이 무게 오름차순 정렬

    sort(arr, arr + cat);

✅ 포인터 left, right를 만들어서 두개의 인덱스로 배열을 검사

		int left = 0;
    int right = cat - 1;
    int count = 0;//행복한 사람 수

    while (left < right) {//두 포인터가 만나기 전까지
        if (arr[left] + arr[right] <= K) {
            left++;   // left는 증가
            right--;  // right를 감소
            count++;
        } else {
            right--;  // 합이 K를 넘으면 right만 감소
        }
    }   

☘️ 투 포인터 ( 시간 복잡도를 낮추는데 효율적 )

투 포인터(Two Pointers)는 주로 배열이나 리스트에서 사용되는 알고리즘 기법 , 두 개의 포인터(인덱스)를 사용하여 배열 내의 요소를 효율적으로 조작하고 탐색하는 방법이다.

⭐️ 주로 이용되는 상황

1. 정렬된 배열에서의 합 탐색:
   투 포인터는 정렬된 배열에서 두 요소의 합, 차, 또는 특정 조건을 만족하는 부분 배열을 찾는 데 유용하다. 정렬된 배열에서 양 끝단의 포인터를 조절하면서 원하는 조건을 찾아나갈 수 있다.
2. 부분 배열의 합 또는 길이에 대한 조건 탐색:
   투 포인터는 배열이나 리스트에서 특정 부분 배열의 합, 길이, 또는 특정 조건을 만족하는 부분 배열을 찾는 데 활용된다.

여기서는 주로 첫 번째 상황을 고려하여 투 포인터를 사용했다. 다음은 투 포인터의 구체적인 작동 방식이다:

• 초기화: 배열이나 리스트를 정렬한 후, 두 개의 포인터를 배열의 양 끝단에 위치시킨다.
• 포인터 이동: 두 포인터 중 하나를 이동시키면서 배열의 특정 위치에서 조건을 확인한다. 이때, 포인터를 이동시킬 때는 주로 정렬된 배열을 다룰 때 사용하는 이진 탐색이나 특정 조건에 따라 적절히 이동시킨다.
• 조건 확인: 포인터의 위치에서 조건을 확인하고, 조건에 맞는 경우 원하는 작업을 수행한다.
• 반복: 조건을 만족하는 경우에는 행복한 사람의 수를 늘리거나 다음 조건을 확인하기 위해 다음 포인터를 이동시킨다. 반복하면서 원하는 결과를 얻을 때까지 진행힌다.

투 포인터를 사용하면 반복문을 한 번만 사용하여 원하는 조건을 찾을 수 있으며, 일반적으로 시간 복잡도가 낮아지는 효과를 얻을 수 있다.

---

처음에 생각했던 풀이

#include <iostream>
#include <algorithm> 
// sort 함수를 사용하기 위한 헤더
using namespace std;

int main() {
    int cat, K; 
    cin >> cat >> K;

    int arr[cat]; // 고양이 무게 배열 입력
    for (int i = 0; i < cat; i++) {
        cin >> arr[i];
    }

    // 무게 오름차순 정렬
    sort(arr, arr + cat);

    // 배열에서 두 마리의 고양이 무게를 더해서 K를 넘지 않으면 행복한 사람 추가
    int count = 0; // 행복한 사람

    for (int i = 0; i < cat; i++) 
        for (int j = i + 1; j < cat; j++) 
            if (arr[i] + arr[j] <= K) {
                count++;
                break; // 한 번의 반복에서 한 쌍의 고양이만 선택하도록 중복 선택 방지
            }

    cout << count << endl;
    return 0;
}

✅ 고양이 수, 버틸수 있는 무게, 고양이 무게 배열 입력 받기

    int cat, K; 
    cin >> cat >> K;

    int arr[cat]; // 고양이 무게 배열 입력
    for (int i = 0; i < cat; i++) {
        cin >> arr[i];
    }

✅ 고양이 무게 오름차순 정렬

    sort(arr, arr + cat);

✅ 이중 배열을 만들어서 고양이 두마리를 뽑아서 무게가 k를 넘는지 검사하고

넘지 않으면 행복한 사람 수 증가

 int count = 0; // 행복한 사람

    for (int i = 0; i < cat; i++) 
        for (int j = i + 1; j < cat; j++) 
            if (arr[i] + arr[j] <= K) {
                count++;
                break; // 한 번의 반복에서 한 쌍의 고양이만 선택하도록 중복 선택 방지
            }

‼️ 이렇게 풀었는데 결과가 틀렸다고 나와서 다른 풀이 방법을 생각해봤다.

( 왜 틀렸는지 모르겠음)