백준 16287번 [Parcel](C++) -yes6686- 티스토리

백준 문제 풀이: 16287 [Parcel]

---

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

문제 설명:

주어진 무게 w를 네 개의 서로 다른 원소의 합으로 만들 수 있는지를 확인하는 문제입니다.

배열의 원소를 두 개씩 묶어서 합을 구한 후, 나머지 두 개가 해당 값과 일치하는지 확인하는 방식으로 풀 수 있습니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int arr[5001]; // 원소 배열
pair<int, int> arrs[400001]; // 두 수의 합을 저장하는 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int w, n;
    cin >> w >> n; // 목표 무게 w, 원소 개수 n 입력

    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // 배열 입력
    }

    sort(arr, arr + n); // 배열 정렬

    // 두 개의 원소 합을 저장
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            arrs[arr[i] + arr[j]] = { arr[i], arr[j] };
        }
    }

    // 다시 두 개의 원소를 뽑아서 확인
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int s = w - (arr[i] + arr[j]); // 필요한 나머지 두 원소의 합
            if (s <= 2 || s > 400000) continue; // 범위를 벗어나면 제외
            if (arrs[s].first == 0) continue; // 존재하지 않는 경우 제외
            if (arrs[s].first != arr[i] && arrs[s].first != arr[j]
                && arrs[s].second != arr[i] && arrs[s].second != arr[j]) {
                cout << "YES" << '\n'; // 네 개의 원소가 존재하면 YES 출력 후 종료
                return 0;
            }
        }
    }

    cout << "NO" << '\n'; // 찾을 수 없는 경우 NO 출력
}

예제 입력:

20 5
2 3 5 7 9

예제 출력:

NO

---

코드 설명

• 핵심 알고리즘: 두 개의 원소 합을 저장한 후, 나머지 두 개를 찾는 방식 (Two-Pointer + Hashing)
• 구현 세부사항:
  • 모든 두 원소의 합을 arrs 배열에 저장
  • 다른 두 개의 원소를 선택하여, w에서 현재 선택한 두 개를 뺀 값이 존재하는지 확인
  • 네 개의 원소가 모두 달라야 하므로 조건을 추가하여 체크
• 시간 복잡도: O(N²), 두 개의 원소 합을 계산하는 과정과 검색 과정이 O(N²)이므로 전체적으로 O(N²)

---

결과

배열에서 네 개의 서로 다른 원소를 합하여 w를 만들 수 있는지 효율적으로 탐색합니다. 해시 테이블과 조합 탐색을 활용한 문제 해결을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!