백준 26091번 [현대모비스 소프트웨어 아카데미](C++) -yes6686- 티스토리

백준 문제 풀이: 26091 [현대모비스 소프트웨어 아카데미]

---

문제 링크: https://www.acmicpc.net/problem/26091

문제 설명:

n개의 물고기의 무게가 주어졌을 때, 두 물고기의 무게 합이 m 이상이 되는 경우의 수를 구하는 문제입니다. 두 물고기를 선택했을 때, 해당 조건을 만족하면 한 쌍으로 간주합니다. 각 물고기는 한 번만 사용 가능하며, 두 포인터 알고리즘을 이용하여 효율적으로 해결할 수 있습니다.

---

문제 해결 코드

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

int arr[100001]; // 물고기 무게 배열

int main() {
    int n, m;
    cin >> n >> m; // 물고기 수와 무게의 최소 합

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

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

    int s = 0; // 시작 포인터
    int e = n - 1; // 끝 포인터
    int cnt = 0; // 조건을 만족하는 쌍의 수

    while (s < e) {
        if (arr[s] + arr[e] < m) {
            // 무게 합이 m보다 작으면 시작 포인터 이동
            s++;
        } else {
            // 조건을 만족하면 쌍의 수 증가 후 포인터 이동
            cnt++;
            s++;
            e--;
        }
    }

    // 결과 출력
    cout << cnt;
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 두 포인터 알고리즘을 사용해 무게 합이 m 이상인 쌍을 효율적으로 찾습니다.
  • 배열을 정렬한 후, 가장 가벼운 물고기와 가장 무거운 물고기를 비교하며 진행합니다.
• 구현 세부사항:
  • 무게 배열을 정렬하여 두 포인터를 설정합니다.
  • 두 물고기의 무게 합이 m 이상이면 쌍의 개수를 증가시키고 양쪽 포인터를 이동합니다.
  • 합이 m보다 작으면 시작 포인터를 이동하여 합을 키웁니다.
• 시간 복잡도 분석:
  • 정렬: O(n log n)
  • 두 포인터 탐색: O(n)
  • 전체 복잡도는 O(n log n)으로 효율적입니다.

---

결과

주어진 물고기 무게 배열과 m값에 따라 조건을 만족하는 쌍의 개수를 효율적으로 계산합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!