[BOJ] 1208 부분수열의 합2

1208번: 부분수열의 합 2

 

문제

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

입력

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

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

---

어제에 이어서 설명이 심플한 문제를 풀어봤다. 처음에는 연속된 부분 배열만 가능한 줄 알고 도대체 이게 왜 골드1이지...? 싶었는데 그냥 내가 문제 이해를 잘못한거였다. 만약 내가 처음 이해한대로의 문제였다면 N이 40밖에 안됐을리가 없지.O(N^2)이 아니라 O(2^40)인 문제였다.

 

어떤 식으로 접근해야하는지 모르겠어서 다른 사람들의 블로그를 참고했다. 한번도 해본 적 없는 방법으로 문제를 풀고있었다. 평소에 내가 접하던 분할 정복의 경우엔 문제를 한번만 쪼개는게 아니라 계속 쪼개는데 이 방법은 문제를 한번만 반으로 나눈다. 그래서 최악의 경우에 2^{(N/2)+1}번의 연산이 있을 수 있다. 2^40에서 이 정도면 파격적으로 줄어든거지. 

 

문제 해결의 아이디어는 일단 수열을 왼쪽과 오른쪽으로 나누고 각각 부분 수열의 합을 구한다. 나 같은 경우엔 왼쪽 수열을 먼저 구했다. 오른쪽을 먼저해도 전혀 지장 없다. 재귀 호출을 이용해 부분 수열 합을 구하는 함수를 작성했고,  STL의 map 자료구조를 사용한다. 수열의 인덱스를 하나씩 증가시켜가면서 인덱스에 해당하는 원소를 더하거나 그냥 지나간다. 그래서 수열 끝에 도달하면 map을 사용해서 부분 수열의 합이 몇개인지 저장한다. 

 

그 다음에 오른쪽도 같은 방법으로 부분 수열의 합을 구하다가 수열의 끝에 도착하면 S에서 이번 부분 수열의 합을 뺀만큼이 왼쪽에서 몇개 있었는지 확인한다. 그걸 정답에 더해주면 된다. 마지막에 S가 0인 경우에 왼쪽과 오른쪽에서 중복으로 세어지기 때문에 -1만 해주면된다.

 

후기)

사실 map을 사용해보지 않아서 처음에 이게 뭐지 싶었는데 key와 value를 묶는 것이 약간 파이썬의 튜플?이랑 비슷한 개념인 것 같다. 사실 파이썬도 잘 모르기 때문에 이게 맞는건진 모르겠다. 하지만 잘 사용하면 확실히 여기저기에 잘 사용할 수 있을 것 같다.