[자바] 백준 18114 - 블랙 프라이데이 (boj java)

문제 : boj18114

 

1. 한 개만 선택해서 C가 되는 경우 (코드 19~22line 참고)

  이 경우는 간단하다. N개를 입력받으면서 해당 값이 C인 경우를 찾으면 된다. O(N)

 

2. 두 개를 선택해서 C가 되는 경우 (코드 24~31line 참고)

  이 경우도 어렵지 않다. 미리 N개를 입력받으면서 배열에도 기록해두고, HashSet에도 기록을 해둔다고 해보자. 이후 배열을 순회하면서 현재 보고 있는 값이 A라고 할 때, HashSet에 C-A가 존재하는지만 확인해주면 된다. 주의점은 A != C-A 여야 한다(동일한 물건을 두 개 고르면 안되고, 모든 물건은 무게가 다르므로 A와 C-A가 동일할 수 없다). O(2N)

 

3. 세 개를 선택해서 C가 되는 경우 (코드 32~41line 참고)

  이 경우가 보통 어렵게 생각할텐데, 사실 '2'랑 똑같다! 2개를 골라 만들 수 있는 모든 쌍의 합 생각해보자. 이건 O(N^2)으로 찾을 수 있을 것이다. 그리고 해당 모든 쌍에서 현재 보고 있는 값이 B라고 한다면, 이번에도 마찬가지로 C-B가 HashSet에 존재하는지만 확인해주면 된다. 주의점은 B가 a+b라 한다면 C-B!=a 이고 C-B!=b 여야 한다(마찬가지로 동일 한 물건을 고르면 안되므로). 최종적으로 O(N^2)이 될 것이다. 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        HashSet<Integer> hs = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            arr[i] = cur;
            hs.add(cur);
            if (cur == c) {
                System.out.println(1);
                return;
            }
        }
        for (int i = 0; i < n; i++) {
            int remain = c-arr[i];
            if (arr[i] == remain) continue;
            if (hs.contains(remain)) {
                System.out.println(1);
                return;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int remain = c-(arr[i]+arr[j]);
                if (remain == arr[i] || remain == arr[j]) continue;
                if (hs.contains(remain)) {
                    System.out.println(1);
                    return;
                }
            }
        }
        System.out.println(0);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}