백준 - 투 포인터 1450 냅색 문제 / 문제풀이, 오답

= 내가 접근 방법 ( 틀림 ) =

처음 내가 접근한 방법은 부분합을 구할 때 사용한 알고리즘을 이용했다.

처음 합은 0 

 

0 <= c이기 때문에 end++

 

0번 index의 값을 더했을 때, 1

 

1 <= c end ++ = > 2, 머 이런식으로 되기 때문에 애초에 접근을 잘못했다.

 

부분합을 구하는 알고리즘을 이 문제에 적용할 수 없다.

 

= 접근 방법 ( 해설 보고 해결 완료 ) = 

 

1. 수가 엄청나게 많기 때문에 시간 복잡도를 고려해야 됨, 따라서 이분 탐색 알고리즘 이용

2. 배열에 담겨있는 수를 반으로 나누어서 각각 새로운 List에 다시 담는다.

3. 재귀를 이용해서 모든 경우의 수(합)를 다 담는다.

예를 들면,

2 1 

1 1        이라는 예제 1번

 

A라는 List에 0, 1을 담을 수 있다. ( 가방에 안 넣었을 때, 하나만 넣었을 때)

B라는 List에 0, 1을 담을 수 있다. 

 

4. 이분 탐색을 이용해서 ( B는 정렬시킴 )

a의 값을 하나 하나씩 넣고 b의 값과 비교해서 값을 다 더하면 정답이다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    public static int[] arr;
    public static int n, c;
    public static List<Integer> a, b;
    public static int index;
 
    public static void main(String[] args) throws IOException {
 
        // 1. input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken()); // n개의 물건
        c = Integer.parseInt(st.nextToken()); // c만큼 담을 수 있는 가방 ( 무게 )
 
        arr = new int[n]; // n개의 물건을 담는 배열
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        // 2. 반으로 나누어서, 담을 수 있는 모든 경우의 수를 센다.
            /*
            예를 들면, 1 2 3 4가 있으면 (1, 2) (3, 4)로 나누고
            (0), (1), (2), (3) 이런식으로 담는다. ( 새로운 배열에 ) => 재귀를 이용하자
             */
 
        a = new ArrayList<>(); // 담을 수 있는 모든 경우의 수 (half)
        b = new ArrayList<>();
 
        dfsA(0, 0);
        dfsB(n / 2, 0);
 
 
        Collections.sort(b);
 
        // 경우의 수가 너무 많기 때문에 이분 탐색으로 값을 확인한다. 어떻게?
            /*
            List<Integer> a 의 값을 a.get(0, 1, 2, .... a.size)까지 넣으면서
            List<Integer> b 의 값 즉 정렬 된 배열 안에서 이분 탐색 알고리즘을 사용한다.
            a.get(0)의 값이 0이라고 가정하면 b의 절반의 값을 더했을 때 c보다 작거나 같다?
            그러면 그 인덱스 + 1을 하면 개수르 구할 수 있다.
             */
 
        int answer = 0;
        for (int i = 0; i < a.size(); i++) {
            index = -1;
            binarySearch(0, b.size() - 1, a.get(i));
            answer += index + 1;
        }
 
        System.out.println(answer);
    }
 
    public static void binarySearch(int l, int r, int aValue) {
 
        while (l <= r) {
            int mid = (l + r) / 2;
 
            if (b.get(mid) + aValue <= c) {
                index = mid;
                l = mid + 1;
            } else if (b.get(mid) + aValue > c) {
                r = mid - 1;
            }
        }
    }
 
 
    // 재귀를 이용해서 모든 합을 담는 메서드
    public static void dfsA(int i, int sum) {
        if (sum > c) {
            return;
        }
 
 
        if (i == n / 2) {
            if (sum <= c) {
                a.add(sum);
            }
            return;
        }
 
        dfsA(i + 1, sum);
        dfsA(i + 1, sum + arr[i]);
    }
 
    public static void dfsB(int i, int sum) {
        if (sum > c) {
            return;
        }
 
        if (i == n) {
            if (sum <= c) {
                b.add(sum);
                return;
            }
        }
 
        dfsB(i + 1, sum);
        dfsB(i + 1, sum + arr[i]);
    }
}