[BOJ 16287] Parcel (ICPC 2018)

문제 출처 : https://www.acmicpc.net/problem/16287

 

풀이 :

 

4개의 무게의 합이 w가 되는 조합이 있는지 물어보는 문제입니다.

단순하게 생각하면 nC4로 4중포문을 도는 방법을 생각 할 수 있겠지만, 이방법은 N이 5000이니 거의 불가능 하다고 판단이 됩니다.

그러므로 one + two + three + four = w 의 형식을 살짝 바꿔서

one + two = w - three - four 의 형식으로 바꿉니다.

그러면 one + two를 구하는 문제로 바뀌게 됩니다.

 

#include<stdio.h>
 
int w, n, arr[5000], wei[800000];
 
int main()
{
    scanf("%d %d", &w, &n);
    for (int i = 0; i < n; i++)scanf("%d", &arr[i]);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (arr[i] + arr[j] > w)continue;
            if (wei[w - arr[i] - arr[j]])
            {
                printf("YES");
                return 0;
            }
        }
        for (int j = 0; j < i; j++)if(arr[i]+arr[j]<w)wei[arr[i] + arr[j]] = 1;
    }
    printf("NO");
}