문제 풀이

n이 최대 5000이므로 단순히 재귀를 통해서 조합을 구하는 것은 무리라고 판단된다.

1개, 2개, 3개를 선택할 때마다 각각 이분탐색을 사용한다면 O(logN) , O(nlogN), O($N^2logN$) 으로 시간안에 통과할 수 있을것 같다.

먼저 정렬을 한 후,
1개를 선택할 때는 그냥 이분탐색을 돌리고,
2개를 선택할 때는 1중 for문으로 한개를 선택하고 나머지를 l을 i+1로 잡고 찾아주면 되고,
3개를 선택할 때는 2중 for문으로 두개를 선택하고 나머지를 l을 j+1로 잡고 찾아주면 된다.

문제 링크

boj/18114

소스코드

PS/18114.java

        import java.io.*;
    import java.util.*;


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        public static void main(String[] args) throws IOException {
            int n,c;
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            int [] arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++)
            {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(arr);
            int l = 0, r = n-1;

            while(l<= r)
            {
                int mid =(l+r)/2;
                if(arr[mid] > c)
                {
                    r= mid - 1;
                }
                else if( arr[mid] == c)
                {
                    bw.write("1");
                    bw.flush();
                    return ;
                }
                else
                    l = mid + 1;
            }
            for(int i=0;i<n;i++)
            {
                int val = 0;
                if(arr[i] < c) {
                    val = c - arr[i];
                    l = i+1;
                    r = n - 1;
                    while (l <= r) {
                        int mid = (l + r) / 2;
                        if (arr[mid] > val) {
                            r = mid - 1;
                        } else if (arr[mid] == val) {
                            bw.write("1");
                            bw.flush();
                            return;
                        } else
                            l = mid + 1;
                    }
                }
            }
            for(int i=0;i<n;i++)
            {
                for(int j=i+1;j<n;j++)
                {
                    int val = 0;
                    if(arr[i] + arr[j] < c)
                    {
                        val =c - arr[i]- arr[j];
                        l = j+1;
                        r = n - 1;
                        while (l <= r) {
                            int mid = (l + r) / 2;
                            if (arr[mid] > val) {
                                r = mid - 1;
                            } else if (arr[mid] == val) {
                                bw.write("1");
                                bw.flush();
                                return;
                            } else
                                l = mid + 1;
                        }
                    }
                }
            }
            bw.write("0");
            bw.flush();

        }

    }