[BOJ] 1208 부분수열의 합 2 - JAVA

1. 문제

1208번: 부분수열의 합 2

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

---

2. 풀이

N이 40까지라서 [1182 부분수열의 합]문제처럼 부분집합을 이용하면 안된다. 2^40은 시간초과가 나기 때문이다.

따라서 입력받은 배열을 둘로 나눠서 오른쪽, 왼쪽 집합 각각 부분집합으로 가능한 모든 경우의 수를 찾으면 2^21번으로 찾을 수 있다.

1) 오른쪽 집합으로 만들 수 있는 경우의 수를 찾아 count배열에 저장한다.

2) (만들어야 하는 수 S - 왼쪽 집합으로 만들 수 있는 부분수열의 합)을 답에 더한다. 

 

static 변수

주어지는 정수에는 음수도 있기 때문에 음수를 양수로 만들 수 있는 충분한 크기의 값이 필요하다. 나는 200만으로 설정했는데, 정수의 절댓값 10만 * 정수 최대 개수 20(40의 절반) = 200만이기 때문이다.

S 범위로만 보면 count 배열 크기도 400만+1로 충분하지만, 따로 범위체크를 하지 않기 위해 800만+1로 설정했다.

int[] arr	입력받은 수열
int N,S	입력받은 수열 길이, 찾아야 하는 수
int[] count	가능한 부분집합의 합 경우의 수
long answer	정답. 최대가 2^40이기 때문에 long타입이어야 한다.
int BASE	음수가 되지 않게 하는 수. 정수의 절댓값 10만 * 정수 최대 개수 20(40의 절반) = 200만

 

main

위의 설명과 동일하다.

오른쪽 배열로 가능한 부분집합 합 경우의 수를 찾고, 그 수를 이용해서 답을 찾는다.

만약 S==0이라면 오른쪽과 왼쪽 모두에서 포함시킨 공집합의 중복을 막기 위해 answer에서 1을 뺀다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   N = Integer.parseInt(st.nextToken());
   S = Integer.parseInt(st.nextToken());

   arr = new int[N];
   st = new StringTokenizer(in.readLine());
   for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());

   count = new int[8_000_001];//정수 절댓값 100,000 * 정수 개수 20(40/2)
   findHalf(N/2,0);
   countAns(0,0,N/2);

   if(S==0) answer-=1;
   System.out.println(answer);
}

 

부분 수열의 합

[1182 부분수열의 합]과 동일하지만 BASE를 더하는 것이 다르다. 음수를 막기위한 것이다.

type을 나눠서 오른쪽, 왼쪽을 처리한다.

오른쪽이라면 경우의 수를 구하고, 왼쪽이라면 경우의 수를 구한 값을 전체 답(answer)에 더한다.

현재 위치 요소를 추가한 것, 추가하지 않은 것 모두 재귀호출한다.

private static void find(int idx, int sum, int end, boolean type) {
   if (idx == end) {
      if (type) ++count[BASE + sum];
      else answer += count[S - sum + BASE];
      return;
   }
   find(idx + 1, sum + arr[idx], end, type);
   find(idx + 1, sum, end, type);
}

 

 

전체 코드

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

public class BOJ_1208_부분수열의합2_2 {
   static int[] arr, count;
   static int N, S, BASE = 2_000_000;
   static long answer;

   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());
      S = Integer.parseInt(st.nextToken());

      arr = new int[N];
      st = new StringTokenizer(in.readLine());
      for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

      count = new int[8_000_001];
      find(N / 2, 0, N, true);
      find(0, 0, N / 2, false);

      if (S == 0) answer -= 1;
      System.out.println(answer);
   }

   private static void find(int idx, int sum, int end, boolean type) {
      if (idx == end) {
         if (type) ++count[BASE + sum];
         else answer += count[S - sum + BASE];
         return;
      }
      find(idx + 1, sum + arr[idx], end, type);
      find(idx + 1, sum, end, type);
   }
}

---

3. 결과

처음에 구간합처럼 간단하게 생각했다가 틀렸다. 순서를 유지하는 게 중요하기 때문에 그 방식으로 구하면 안된다.

map을 사용했을 때보다 배열을 사용했을 때 훨씬 속도, 메모리면에서 유리했다. (당연한 결과다)