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

문제

 

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

1208번: 부분수열의 합 2

 

풀이

 

solved.ac 난이도: Gold 1

 

원소가 부분수열에 포함되는지 여부를 경우의 수로 생각해 보자.

포함되느냐 안되느냐인 두 가지 선택을 40개의 수에 적용하면 2^40 가지의 경우가 나온다.

2^40 = 1,099,511,627,776(약 1TB) 이므로 시간 안에 동작시킬 수 없다.

 

여기서 사용되는 기법이 양방향 탐색(Bidirectional serach)이다.

양방향의 효율성은 다음 그림과 같이 표현할 수 있다.

기본적인 탐색이라면 모든 경우의 수를 탐색해 나가면서 점점 그 범위가 넓어지는데,

이를 양쪽에서 시작하도록 바꾸면 나머지 흰 공간에서는 탐색할 필요가 없어진다.

 

 

이번 문제에서는 수열을 반으로 left, right 나누어 진행하자.

40을 반반으로 나누면, 2^20 = 1,048,576으로 충분히 진행할 만하다.

 

[left에서 만들어진 부분 수열합] + [right에서 만들어진 부분 수열합] = S이다.

 

좌변의 값을 우변으로 옮기면 

[left에서 만들어진 부분 수열합]  = S - [right에서 만들어진 부분 수열합]으로 만들 수 있다.

 

이제 left에서 만들어지는 부분 수열 합의 개수를 map<부분 수열 합, 카운트>로 저장시키고,

{S - [right에서 만들어진 부분 수열합]} 이 map의 key로 존재한다면 부분수열로 S를 만들 수 있다.

 

이때 부분 수열은 공집합을 제외하기 때문에 S가 0이면 공집합을 제외해 주자.

 

코드

 

 

 

 

참조 풀이

https://hyeo-noo.tistory.com/128

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