[백준 1208번] 부분수열의 합 2 (java)

1208번: 부분수열의 합 2

주어진 배열 전체를 가지고 부분수열의 합을 구하면 시간초과가 난다.

그러므로 이 문제를 배열을 두 개로 나누어서 투 포인터 알고리즘으로 부분수열의 합을 구해야 한다.

 

처음에는 부분수열이 연속해야만 하는 줄 알았는데, 문제를 다시 읽어보니 꼭 연속하지 않은 수열이어도 상관없다는 것을 깨달았다.

 

알고리즘

1. 먼저 배열을 두 개로 나눈다. (0 ~ N/2), (N/2 ~ N)

   예를 들어, 문제 예제에서 주어진 배열이 -7 -3 -2 5 8 이면 -7 -3 / -2 5 8 이렇게 나눌 수 있다.

 

2. 나누어진 두 개의 배열에 대해 각각의 경우 나올 수 있는 모든 부분수열의 합을 구한다.

   이 때, 재귀를 사용하여 부분 수열의 합을 구할 수 있다.

   아래의 코드처럼 재귀를 이용하여 부분 수열의 합을 구하다보면, sum = 0 인 경우가 생기게 된다.

   두번째 재귀함수를 호출할 때를 보면 sum에 아무것도 더하지 않고 인자로 넘기기 때문이다.

	public static void getSubsequence(int idx, int end, long sum, List<Long> list) {

		if (idx == end) {
			list.add(sum);
			return;
		}

		getSubsequence(idx + 1, end, sum + arr[idx], list);
		getSubsequence(idx + 1, end, sum, list);
	}

   먼저, 왼쪽 부분인 -7 -3 을 보면 가능한 부분수열의 합은 -10(-7 + -3), -7, -3, 0 이 된다.

   오른쪽 부분 -2 5 8 도 가능한 부분수열의 합을 구하면 -2, 3(-2+5), 6(-2+8), 5, 8, 13(5+8), 0  이 된다. 

 

3. 투 포인터 알고리즘을 위해 두 개의 리스트(부분수열의 합이 들어가 있음)를 각각 정렬한다.

•    left : -10  -7  -3  0

•    right : -2  0  3  5  6  8  13

   투 포인터 알고리즘에 대해 잘 모른다면, 아래 링크를 참고한다.

    lotuslee.tistory.com/30?category=963570

투 포인터 알고리즘 - 2. 다른 방향(배열 2개)

    

4. 정렬된 두 리스트를 이용하여 투 포인터 알고리즘을 진행한다.

    투 포인터를 통해 두 리스트의 요소의 합이 S와 같은 경우에만 count를 증가시키면 된다.

 

    그런데 생각해봐야 할 것이 있다.

    두 리스트의 합이 S가 되는 경우도 있지만 left 리스트에 있는 부분수열의 합만으로 S가 되거나,

    혹은 right 리스트에 있는 부분수열의 합만으로 S가 되는 경우도 있을 것이다.

    하지만 투 포인터를 통해서 이 두가지 경우도 모두 구할 수 있다. 왜냐하면 각각의 리스트에 공집합 0이

    존재하기 때문이다.

 

    left : -10  -7  -3  0

    right : -2  0  3  5  6  8  13

 

    이와 같이 정렬된 두 개의 리스트가 있을 때, 만약에 left 리스트에 있는 -10 과 right 리스트에 있는 0을

    더할 경우, -10 + 0 = -10 이므로 결과적으로 left 리스트에 있는 부분수열의 합을 구하는 것이기 

    때문이다.

    즉, 두 리스트에 공집합 0이 포함되어 있기 때문에 투 포인터 알고리즘을 진행하면서

    left 리스트에만 있는 부분수열의 합이나 right 리스트에 있는 부분수열의 합도 구할 수 있게 된다.

 

    그렇기 때문에 만약에 S = 0 이라면, 두 리스트에 있는 공집합끼리 더해서 0 + 0 = 0가 되어

    S = 0을 만족하는 경우가 생기게 되는데, 이 때의 0은 제외시켜야 하므로

    최종 count에서 1을 빼줘야 한다. -> count--

 

 

소스코드 :