BOJ-16287 Parcel

접근

• 너무 오랜만에 백준에 들어갔고 알림에 가장 위에떠있는 재채점 후 틀린 문제였다. 진짜 이문제 처음 접했을때가 이제 막 알고리즘이 이런거구나 알아가던 때였는데 세상 반갑고 세상 알고리즘 오랜만에해서 반성 많이 했다.

• 기존의 풀이방식은 a + b + c + d = w 식을 a + b -> A로 c + d -> B로 바꾸어 풀어내는 방식이었다. 그렇게하면 n^4를 n^3으로 풀어낼 수 있었고, 통과했었었다. n^3에서 더 줄일 수 있는 곳은 중복체크를 개선해야한다고 생각했고 dp를 사용하는 방법을 생각했다.

• dp[두 무게의 합] = 두 무게의 인덱스 중 큰 값으로 정의하고 for문으로 두 무게를 선택 후 dp[w - 선택한 두 무게의 합]의 값이 현재 선택한 두 무게 중 더 작은 인덱스의 값보다 작다면 4개의 무게가 중복되지 않는다는 것이므로 YES를 출력하고 종료하게 했다.

코드(C++)

#include <iostream>
#include <algorithm>
#define FIO  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;

int w,n,arr[5010],dp[800010];

int main(){
    FIO;
    cin>>w>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int s = arr[i]+arr[j];
            if(w-s<=0) continue;
            else if(dp[w-s] && dp[w-s]<i) {
                cout<<"YES";
                return 0;
            }
            dp[s] = (dp[s] ? min(dp[s],j) : j);
        }
    }
    cout<<"NO";
    return 0;
}

결과