[C++] 16287번 Parcel - DP, 중간에서 만나기

#include <iostream>

#define FOR(i, k, N) for(int i=k; i<=N; i++)

using namespace std;

const int MAX_W = 799995;
const int MAX_N = 5001;

//무게 w, 원소 개수 n
int w, n;
//수열
int num[MAX_N];
bool weight[MAX_W];

void input()
{
    cin >> w >> n;
    FOR(i, 1, n) cin >> num[i];
}

int main()
{
    cin.sync_with_stdio(0);
    
    input();
    
    FOR(i, 1, n-1) {
        FOR(j, i+1, n) {
            int s = w - num[i] - num[j];
            if(s < 0) continue;
            if(weight[s]) {
                cout << "YES";
                return 0;
            }
        }
        FOR(j, 1, i-1)
            if(num[i] + num[j] < w)
                weight[num[i] + num[j]] = true;
    }
    
    cout << "NO";
    
    return 0;
}​

자세한 설명은 생략함.

 

sort를 해주면 num[i]+num[j]는 j가 커질수록 항상 더 커지니까 if(s<0)에서 continue가 아닌 break를 함으로써 시간을 더 줄일 수 있다고 한다. 아래에 그런 코드의 링크를 달아놓았다.

 

 

<참조한 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/49240990

로그인

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.