[백준 1208 C++] 부분 수열의 합 2

백준 1208번 부분 수열의 합 2 문제 링크 

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

1208번: 부분수열의 합 2

문제 풀이 

백준 1208번 부분 수열의 합2문제는 백준 1182번 부분 수열의 합 방식대로 문제를 풀면 시간 초과가 난다. 

그 이유는 정수의 개수가 20에서 40으로 늘어났을 뿐만 아니라 시간 2초에서 1초로 바뀌었기 때문이다. 

 

그렇기에, 1208번 같은 경우에는 부분 수열의 합 계산을 나눠서 진행해주어야 한다. 

즉, 1182번에서 진행했던 것을 2번 진행하는 셈인 것이다. 

 

이렇게 2개로 나누었을 때 발생한 경우를 생각해보면, 아래와 같이 경우를 나눌 수 있을 것이다.

1. 집합 A에서 부분 수열의 합이 존재하는 경우

2. 집합 B에서 부분 수열의 합이 존재하는 경우 

3. 집합 A에서 구한 합 + 집합 B에서 구한 합 = 부분 수열의 합인 경우 

 

1,2의 경우에는 1182번에서 했던 것과 동일하게 (0 ~ N/2-1), (N/2 ~ N)으로 나눠서 진행해주면 된다. 

그리고, 3번의 경우에는 1,2 과정에서 나오는 합들을 각각 A,B 벡터에 저장한 후, 두 개의 합이 부분 수열의 합이 되는지 확인하기 위해 S - A[i]를 한 후, 벡터 B에 이 값(S - A[i]) 이 몇 개 존재하는지 찾아주면 된다. 

 

이 문제의 핵심은 작업을 반으로 나눠서 풀어주는 것이었다.