[백준] 16287 Parcel

1. 문제

www.acmicpc.net/problem/16287

16287번: Parcel

2. 접근방법

5000개의 N 중에 4개를 뽑아서 합할때 W에 정확히 맞추는 4개의 숫자가 있는지 찾는 문제

 

간단히 조합으로 해결하려 하면 5000 C 4 무조건 시간초과가 터지니 다른 방법을 찾아야 한다.

 

해결방법은

A + B + C + D = W 에서

A + B = W - C - D 형태로 바꾸어 생각하는 것이다.

 

2중 for문으로

A+B의 값을 계산하고  이에 해당하는 C D값이 있다면 YES출력

없다면

C = A

0 <= D < A

로 생각해고 W - C -D 값을 기록하고 다음 A값으로 넘어간다.

 

이러면 N C 2 + N(N+1)/2 

시간복잡도는 O(N^2) 이 되어 해결이 가능하다.

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G1_16287Parcel {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int W = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int arr[] = new int[N];
		boolean sum[] = new boolean[400001];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		boolean ok = false;
		
		gg:for(int i = 0 ; i < N ; i++) {
			for(int j = i+1 ; j < N ; j++) {
				int now = arr[i] + arr[j];
				if(now >= W || W- now > 400000 )
					continue;
				if(sum[W-now]) {
					ok = true;
					break gg;
				}
			}
			for(int j = 0 ; j < i ; j++)
				sum[arr[i]+arr[j]] = true;
		}
		System.out.println(ok?"YES":"NO");
	}

}

4. 마치며

4개를 뽑아야만 한다는 생각에 빠져서 2개 2개로 나누는 것을 생각해내기가 어려웠던 문제

신선했다.