StepByStep

www.acmicpc.net/problem/16287

문제

국제대학소포센터(ICPC: International Collegiate Parcel Center)는 전세계 대학생들을 대상으로 소포 무료 배송 이벤트를 진행하고 있다. 무료 배송 조건은 보낼 소포가 물품 4개로 구성되어야 하며 이들 물품의 무게 합이 정확히 정해진 정수 무게w그램이어야 한다는 것이다.

부산대학교에 있는 찬수는 영국 왕립대학에 있는 수환에게 보낼 물품이 매우 많이 있는데, 각 물품의 무게(모두 정수 그램)는 모두 다르다. 이 이벤트는 한시적으로 진행되는 이벤트이기 때문에 찬수는 자신이 보낼 물품 중에서 이 조건을 만족하는 물품 4개가 있는지 가능하면 빨리 알아내고 싶다. 다시 말해서 서로 다른n(n≥ 4)개의 정수로 이루어진 집합A에서 4개의 원소만 꺼내어 만든 부분집합B(|B| = 4)가 ∑b∈Bb=w조건을 만족하는지 판단하려고 한다.

주어진w와A에 대해서, 위 조건을 만족하는 부분집합B가 존재하면 YES를, 아니면 NO를 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게w(10 ≤w≤ 799,994)와A의 원소 개수n(4 ≤n≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는A의 원소인n개의 정수ai∈A(1 ≤i≤n)가 공백으로 분리되어 주어진다. 각 원소ai는 1이상 200,000이하이다(1 ≤ai≤ 200,000).

출력

출력은 표준출력을 사용한다. 문제의 조건에 따라YES나NO를 한 줄에 출력한다.

접근 방법

일단 이 문제는 시간 제한이 1초이고, 원소 개수가 5,000개 까지 들어올 수 있으므로 일반적인 조합으로 풀면 시간이 초과하게 된다.

입력받은 수 중에 4개의 합이 w가 되면 되므로 중복으로 계산이 되어야 한다 -> 이를 통해 DP문제 임을 깨달았다.

점화식을 구해야 하는데 먼저 입력 받은 무게를 정렬을 한 뒤 무게를 더해 가는데 4개를 2개 2개로 나뉘면 연산의 횟수가 줄어들어 이를 이용한다.

앞에서 부터 2개를 더한 값을 인덱스로 사용하고, 그 배열에는 무게가 무거운 인덱스를 넣는다. 그리고 그 더한 값을 W에서 빼준 값의 인덱스를 가진 DP가 존재하는지 확인을 하고, 그 인덱스가 2개 더한 값 중 무거운 인덱스보다 크기가 크면 값을 가지게 된다.

이 이유는 2중 포문이 순서대로 돌아가므로 DP배열에 들어 있는 것이 무거운 것만 있어도 중복이 되지 않음을 알 수 있다.

 예시의 경우 i가 2일때 weigth[i][6] = 10 이고, w-10인 dp[11] 에 7이 들어 있으므로 이미 값이 있다는 것은 이전에 만들어 졌다는 것을 의미 하며, 현재 들어있는 7이 6보다 큰 값이므로 dp[11] 은 7번 인덱스와 1번 인덱스, dp[10]은 2번 인덱스와 6번 인덱스 임을 알 수 있다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int w,n;
        w = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        int[] weight = new int[n];
        int[] dp = new int[799994 + 1];
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < n; i++)
            weight[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(weight);

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n ; j++) {
                int tmp = weight[i]+weight[j];
                if(tmp > w)
                    continue;
                dp[tmp] = j;
                if(dp[w-tmp]!= 0 && dp[w-tmp] > j){
                    System.out.println("YES");
                    return;
                }
            }
        }
        System.out.println("NO");
    }
}