[백준] 1208번 - 부분수열의 합 2

https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

 

 

 

문제

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

 

입력

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

 

풀이법

이 문제는 이분탐색을 이용해서 푸는 문제다. 그런데 풀다보니 우연찮게 아래와 같이 DP로 푸는 방법을 발견하였다.

1. 비어있는 수열 SEQ 를 가정한다. SEQ는 문제에서 주어진 수열의 부분수열이다.
2. SEQ의 부분수열의 원소를 모두 더하여 만들 수 있는 값과 그 경우의 수를 기록하는 배열을 만든다. (배열 : sumArr)
3. 주어지는 정수의 절대값은 최대 M이라고 하자. (M=100,000)
4. sumArr의 크기는 80,000,001이다. (부분수열 원소합의 범위가 -40,000,000 ~ 40,000,000 (-N * |M| ~ N * |M|) 임)
5. 수열 SEQ가 비어있으므로 sumArr 배열의 초기값은 모두 0이다. 다만 계산을 위해 원소의 합이 0이 되는 경우의 수를 1로 설정한다. (공집합)
6. SEQ에 문제에 주어진 수열의 원소 a를 하나 추가한다.
7. 원소가 하나 추가되었으므로 sumArr를 업데이트한다. 현재 sumArr에 SEQ에 a를 추가했을때 원소합을 만들수 있는 경우의수를 더한다. (sumArr[i+a] += sumArr[i])
8. 다음 원소들을 추가하면서 마찬가지로 sumArr를 업데이트한다.
9. 모든 원소들을 추가한 뒤에 4번에서 계산을 위해 추가한 경우의 수를 빼준다. (원소합 0이 되는 경우의 수 -1)
10. 답을 출력한다. (sumArr[S])

 

코드

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

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

	private static final int MAX_SUM = 4000000;

    public static void main(String args[]) throws IOException {
    	st = new StringTokenizer(br.readLine());
    	int n = Integer.parseInt(st.nextToken());
    	int s = Integer.parseInt(st.nextToken());

        //입력값을 nums 배열에 저장
    	int[] nums = new int[n];
    	st = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		nums[i] = Integer.parseInt(st.nextToken());
    	}

        //원소의 합을 만드는 경우의 수를 담은 배열 sums 초기화
        //sums[4000000] => 합이 0인 경우의 수
        //sums[0] => 합이 -40,000,000인 경우의 수
    	long[] sums = new long[MAX_SUM*2+1];
    	sums[MAX_SUM] = 1;
        
        //nums의 원소를 하나씩 추가하면서 sums 배열 업데이트
        //더할 경우의 수를 저장하는 diff 배열 이용해 마지막에 sums 한번에 업데이트
    	for(int i = 0; i < n; i++) {
    		long[] diff = new long[MAX_SUM*2+1];
    		for(int j = 0; j < sums.length; j++) {
    			int idx = j + nums[i];
    			if(idx >= 0 && idx < sums.length) {
    				diff[idx] = sums[j];
    			}
    		}
    		for(int j = 0; j < sums.length; j++) {
    			sums[j] += diff[j];
    		}
    	}

        //비어있는 수열의 경우의 수 제거
    	sums[MAX_SUM]--;
        //정답출력
    	bw.write(String.valueOf(sums[s+MAX_SUM]));
    	bw.newLine();

    	bw.flush();
        bw.close();
        br.close();
    }
}

 

시간복잡도

수열의 원소를 SEQ에 추가할 때마다 2*N*|M|+1 크기의 배열을 업데이트하므로 시간복잡도는 O(|M|*(N^2))

실제 연산횟수는 2*40*40*100,000+1 = 3.2 * 10^8. 시간제한이 1초긴하지만 시간제한에 걸리지는 않는다. 아슬아슬하게 통과하는 듯 하다.

 

메모리

sumArr를 int로 선언하면 overflow가 발생한다. sumArr를 long형으로 선언시 8byte * (2*40*100,000+1) = 64MByte

sumArr를 한번에 업데이트하기 위해 같은 크기의 배열(diff)을 하나 더 사용하므로 총 사용하는 메모리는 128MByte.