[백준] 16287 - Parcel (Python)

4개를 모두 골라서 $w$가 맞는지 비교하는 것은 지나치게 큰 비용을 요구한다.

2개씩 골라서 합을 구해 비교하는 방식을 사용해야 한다.
$(i < j < k < l)$ 이며 $a[i]+a[j]+a[k]+a[l] = W$ 을 만족하는 $i, j, k, l$을 뽑는 과정을 보자.

1. 모든 순서쌍 $(i, j)$를 뽑는다. 이때 $DP[a[i]+a[j]] = j$로 저장해 준다.
2. 만약 기존에 $DP[a[i]+a[j]]$ 값이 존재하면 비교해서 더 작은 값을 넣어준다. $j$값이 작으면 작을수록 $j < k$ 에 유리하다.
3. 모든 순서쌍 $(k, l)$에 대해서 $DP[W-a[k]-a[l]] < k$ 를 만족하는지 검사한다.

import sys
input = sys.stdin.readline

w, n = map(int, input().rstrip().split())
arr = sorted(list(map(int, input().rstrip().split())))

mem = [-1 for _ in range(800000)]

def find():
    for i in range(n):
        if arr[i] >= w:
            return False
        for j in range(i+1, n):
            res = arr[i]+arr[j]
            # arr는 정렬되어 있음
            if res >= w:
                break
            # 값이 존재하지 않음
            if mem[res] < 0:
                mem[res] = j
            else:
                mem[res] = min(mem[res], j) 
            # 저장 후 조건에 맞는 값이 존재하는지 찾음
            if mem[w-res] > -1 and mem[w-res] < i:
                return True
if find():
    print('YES')
else:
    print('NO')