[백준] 16287 Parcel

문제 주소 : www.acmicpc.net/problem/16287

16287번: Parcel

문제 확인

 

dp 문제입니다.

dp를 사용하지 않고 4중 포문으로 풀면 n이 5000이기 때문에 시간 초과가 납니다. 따라서 문제를 i + j, w - (i + j) 두 파트로 나누어 문제를 풀어야 합니다.

 

풀이

 

무게를 인덱스로 활용해 만들 수 있는 무게를 기록합니다. 각 원소의 최대 크기는 200000으로 dp[400000]을 사용합니다.

2중 포문으로 지나처온 리스트에서 만들 수 있는 w 값을 배열에 기록해두고 다음 i, j를 사용해 만든 w - (i + j) 값이 기록되어 있다면 Yes를 출력합니다.

입력받은 값을 정렬해 ary[i+1] + ary[j] 값이 필요 이상으로 커지게 되면 break를 통해 탐색 횟수를 줄입니다.

 

코드

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int w, n, ary[5000];
    bool dp[400001] = { 0 };
    scanf("%d%d", &w, &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &ary[i]);
    sort(ary, ary + n);
    for (int i = 0; i < n - 2; i++) {
        for (int j = 0; j < i; j++)
            dp[ary[i] + ary[j]] = true;
 
        for (int j = i + 2; j < n; j++) {
            int t = w - ary[i + 1] - ary[j];
            if (t < 0)break;
            if (t <= 400000 && dp[t]) {
                printf("YES");
                return 0;
            }
        }
 
    }
    printf("NO");
}