# 유형 : 투 포인터, 탐색
# 부분수열의 합 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번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
|
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); } }
|
cs |
'백준' 카테고리의 다른 글
| #백준_1525 퍼즐 - Java (0) | 2020.01.21 |
|---|---|
| #백준_7453 합이 0인 네 정수 - Java (0) | 2020.01.20 |
| #백준_1261 알고스팟 - Java (0) | 2020.01.19 |
| #백준_2261 가장 가까운 두 점 (0) | 2020.01.13 |
| #백준_1517 버블 소트 (0) | 2020.01.13 |
