Parcel( BOJ 16287 )

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

16287번: Parcel

 

문제 파악하기

N개의 숫자 중 4개의 서로 다른 숫자의 합이 정확하게 W를 만족하는 경우가 있는지 찾는 문제입니다. N의 값이 최대 5,000이라 작은 편이지만 모든 경우의 수를 탐색하는 O(N⁴) 알고리즘을 사용하기에는 충분히 큰 숫자입니다. 따라서, 적절한 탐색 기법을 활용해 O(N²) 알고리즘으로 바꾸어야 합니다. 어떻게 해야 알고리즘의 효율성을 높힐 수 있을까요?

 

문제 해결하기

우선, 우리는 W = a+b와 같이 2개의 묶음으로 나눌 수 있습니다. 여기서 a와 b가 의미하는 값은 각각 서로 다른 숫자 2개의 합을 의미합니다. 이렇게 W를 2개의 값으로 바꿔 생각해보면 좋은 점은 바로 a의 값을 따로 구하기만 하면 저절로 우리에게 필요한 b의 값을 구할 수 있다는 점입니다. b의 값은 (W-a)로 표현할 수 있으며, 구한 값이 a에서 사용하지 않은 두 숫자의 합이 있는지 확인하면 우리가 원하는 결괏값을 찾을 수 있습니다. 이제부터 a와 b의 값을 차근차근 구해봅시다.

 

그럼 문제 해결을 위한 첫 번째 단계인 a의 값부터 구해봅시다. a는 N개의 숫자 중 서로 다른 두 숫자의 합을 의미합니다. 그리고 제시된 숫자는 최대 5,000개이기 때문에 중첩 반복문을 사용해도 충분합니다. 따라서, 중첩 반복문을 사용하여 서로 다른 두 숫자의 합을 하나씩 구해보면 됩니다. 이렇께 a를 먼저 구한 다음에는 두 번째 단계인 b를 확인할 수 있습니다. 여기서 확인한다는 의미는 곧 현재 사용한 숫자 이외의 값으로 b를 만들 수 있는지 살펴본다는 의미입니다. 효율적으로 b를 살펴보는 방법으로는 이전에 이미 확인했던 값들을 활용하는 방법이 있습니다. 이미 확인했던 값이란 a = inp[i]+inp[j] (i<j)라고 할 때, inp[i] 이전의 값들로 만들 수 있는 모든 값을 의미합니다. 예를 들어 아래와 같이 7개의 숫자가 있으며, inp[i] = 2, W = 25라고 가정해봅시다.

 

6  10  8  7  2  7  1

 

우리는 inp[i](2)를 사용해 a = (2+7) = 9를 만들 수 있습니다. 그리고 우리가 사용한 두 숫자와 겹치지 않게 이전에 사용했던 숫자들인 (6, 10, 7, 9)를 사용해 b = 25-9 = 17을 만들 수 있는지 확인할 수 있습니다. 마침 10과 7을 사용하면 우리가 원하는 b의 값을 구할 수 있습니다! 이렇게 이전에 사용했던 숫자들의 합을 따로 구해놓은 다음에 b의 값으로 설정할 수 있는지 확인하면 우리가 원하는 시간 내에 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <iostream>
#include <vector>
#define AMAX 400010
using namespace std;
 
int N, W, t, flag;
vector< int > inp;
 
int check[AMAX];
 
int main() {
    // init
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 입력
    cin >> W >> N;
    for(int i=1;i<=N;i++) {
        cin >> t;
        inp.push_back(t);
    }
    
    for(int i=0;i<N and !flag;i++) {
        for(int j=i+1;j<N and !flag;j++) {
            // W = a+b (a와 b는 모두 두 숫자의 합)
            int a = inp[i]+inp[j];
            int b = W - a;
            
            if((0<=b and b<AMAX) and check[b]) flag = 1;
        }
        
        // (0~j)에서 나올 수 있는 모든 a(inp[i]+inp[j])의 경우를 check에 표시하기
        for(int j=i-1;j>=0;j--) check[inp[i]+inp[j]] = 1;
    }
    
    // 출력
    cout << (flag>0 ? "YES":"NO");
}
 

후기

W = a+b에서 a를 구하는 방법은 쉽게 떠올렸지만 b를 파악하는 방법을 쉽사리 떠올리지 못 했던 문제입니다. 어떤 순서든 4개의 숫자를 고른다는 점에만 집중한다면 나름 어렵지 않게 문제를 풀 수 있을 듯 합니다. 탐색의 범위를 줄이는 문제로 소개하기 적절한 문제라고 생각합니다.