#백준_1208 부분수열의 합 2 - Java

# 유형 : 투 포인터, 탐색

# 부분수열의 합 1(https://www.acmicpc.net/problem/1182) 에서는 2^20이어서 2초를 안넘겼지만, 이번 문제는 2^40이고 제한시간은 1초였다. 문제도 제대로 안읽고 1182번에서 푼 대로 접근해보았지만 당연히 시간초과.

어떻게 해결할지 생각해보다가 찾은 방법은 배열을 분할하여 푸는 방법이었다. 2^20은 약 1초만에 계산이 가능하기 때문에 가능한 방법.

[1,3,5,7,2,4,5,10] 을 [1,3,5,7] [2,4,5,10]으로 나누어 왼쪽의 부분집합의 합, 오른쪽의 부분집합의 합을 구하는 리스트를 구한 후, 정렬하여 투포인터 알고리즘을 사용하여 해결한다. 이 때 값들을 long 타입으로 안해줘서 74%정도에서 계속 틀렸습니다가 떠서 한참을 헤맸다.

1182번: 부분수열의 합

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

package bj;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer;   public class p1208 {     static int N,S;     static int arr[];     static ArrayList<Integer> left = new ArrayList<>();     static ArrayList<Integer> right = new ArrayList<>();     static long cnt=0;     public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         N = Integer.parseInt(st.nextToken());         S = Integer.parseInt(st.nextToken());         arr = new int[N];                  st = new StringTokenizer(br.readLine());         for(int i=0; i<N; i++)             arr[i] = Integer.parseInt(st.nextToken());                  makeBinary(0, 0, N/2, left);         makeBinary(0, N/2, N, right);                  Collections.sort(left);         Collections.sort(right);                  int leftIndex = 0;         int rightIndex = right.size()-1;         while(leftIndex<left.size() && rightIndex>=0) {             long left_val = left.get(leftIndex);             long right_val = right.get(rightIndex);                          if(left_val + right_val == S) {                 long left_count = 0;                 while(leftIndex<left.size() && left.get(leftIndex)==left_val) {                     left_count++;                     leftIndex++;                 }                 long right_count = 0;                 while(rightIndex >= 0 && right.get(rightIndex) == right_val) {                     right_count++;                     rightIndex--;                 }                                  cnt += right_count * left_count;             }                          if(left_val + right_val < S) {                 leftIndex++;             }             if(left_val + right_val > S) {                 rightIndex--;             }         }                  if(S==0)             System.out.println(cnt-1);         else             System.out.println(cnt);                                }     public static void makeBinary(int sum, int start, int end, ArrayList<Integer> list) {         if(start >= end) {             list.add(sum);             return;         }         makeBinary(sum, start+1, end, list);         makeBinary(sum+arr[start], start+1, end, list);     } }   Colored by Color Scripter

cs