[백준 16287번 C/C++] Parcel

 

[백준 16287번 C/C++] Parcel

 

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

 

---

 

 

해결전략

 

조합 탐색 (Combination Search), 부분 합  (Subset Sum Problem), 정렬 (Sorting)

여러 숫자 중 특정 개수(이 경우에는 4개)의 숫자를 선택하여 그 합이 특정 값이 되는지 찾는다.
네 숫자의 합이 목표값 w가 되는지를 찾는 것이므로 부분합 문제의 변형으로 볼 수 있다.

---

 

 

정답코드

 

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int w, n; // w: 합의 목표 값, n: 숫자의 개수
    cin >> w >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());

    
    vector<bool> dp(400001, false); // 합이 400000 이하의 값들이 가능한지를 저장할 dp 벡터 생성

    // 첫 번째 루프: 마지막 두 숫자를 제외한 범위에서 두 숫자의 합을 dp에 기록
    for (int i = 0; i < n - 2; i++) 
    {
        for (int j = 0; j < i; j++) {
            dp[v[i] + v[j]] = true;
        }

        // 두 번째 루프: 현재 i+1 이후의 숫자들과 조합하여 조건을 만족하는지 확인
        for (int j = i + 2; j < n; j++) {
            int t = w - v[i + 1] - v[j]; // 목표 값에서 두 숫자의 합을 뺀 값 t 계산

            if (t < 0) break;  // t가 0보다 작다면 더 이상 확인할 필요가 없음 (정렬되어 있기 때문에)
            if (t <= 400000 && dp[t]) {  // t가 400000 이하이고, dp[t]가 true이면, 네 숫자의 합이 w가 되는 경우를 찾음
                cout << "YES" << endl; // 결과 출력
                return 0;              // 프로그램 종료
            }
        }
    }

    cout << "NO" << endl; // 네 숫자의 합이 w가 되는 경우를 찾지 못한 경우
    
    return 0;
}

 

 

---