-
[Python 3] BOJ - 1208 "부분수열의 합 2"BOJ 2020. 4. 18. 13:29
# 문제 링크 : https://www.acmicpc.net/problem/1208
# 풀이 :
개인적으로 이 문제는 부분수열의 합1의 이분탐색 버전이라고 생각한다. 길이가 N인 수열의 부분수열의 전체 경우의 수는 2의 N승인데, 문제에서 N이 40이므로 2 ^ 40 = 1,099,511,627,776이므로 시간초과를 피할 수 없다. 따라서 수열을 반으로 나눈다면 2 ^ 20 = 1,048,576이므로 부분집합을 크게 두 부분으로 구할 수 있다. 따라서, 두 부분을 탐색하면서 각각의 합이 S면 순서쌍을 세어주면 정답을 구할 수 있다
현재 수열이 {-7,-3,-2,5,8}인 상황이라고 가정하자. 이 경우는 크기가 작아 32번만에 모든 부분집합을 구할 수는 있지만 위 단락에서 본 바와 같이 두부분으로 나누어서 구해보겠다. 따라서, 좌측의 Subset중 하나를 고르고, 우측의 Subset중 하나를 고르면 모든 부분집합에 대해 표현이 가능하다. 즉, 분할하여 구할 수 없는 {-7,-3,-2,5}의 경우, 좌측의 {-7,-3,-2}를 고르고 우측의 {5}를 고르면 충분히 표현이 가능하다.
그러나 우리는 부분집합의 합이 S가 되는 경우를 구해야 하므로 좌측의 각각의 Subset의 합을 left에, 우측의 각각의 Subset의 합을 right에 저장하면 위 그림2와 같이 됨을 알 수 있다. 이 때 S는 0이라고 가정하자. 이 때 left와 right에 대한 포인터를 각각 f,r이라고 하자. 현재의 경우 left[f] + right[r]의 경우는 1로서 0보다 크다. 그렇다면 두가지 경우가 존재한다.
f를 이동하는 것과 r을 이동하는 것인데, 현재 left는 오름차순으로 정렬되어 있고, right는 내림차순으로 정렬되어 있다. 따라서, r을 이동시켜야 한다. 같은 논리로 left[f] + right[r]이 S보다 작다면 f를 이동시켜야 한다. 만일 S라면 f와 r 모두 이동시켜야 한다.
따라서 위 그림 2에서는 f가 4, r이 2일 때와 f가 7, r이 3일 때 left[f] + right[r] = 0이므로 가능한 순서쌍은 2개라고 할 수 있다. 그런데, 문제의 조건에서 부분집합이 공집합은 경우를 제외한다고 했으므로 S가 0인 경우는 left, right가 모두 공집합인 경우를 빼줘야 한다.
위 그림 3에서 left[f1] + right[r1]이 S이므로 한가지 쌍이 추가된다. 위 단락의 움직이는 경우에 따라 S와 같으므로 f1과 r1은 각각 한칸씩 움직여 f2,r2가 된다. 그런데 만일 여기서 바로 left[f2] + right[r2]를 비교하게 되면, (f1, r2), (f1, r3)의 경우를 놓치게 되므로 left와 right 모두 한칸 움직였을 때도 움직이기 전과 같은 수라면 쌍을 추가할 수 있기 때문에 더이상 같은 수가 나오지 않을 때 까지 갯수를 세어주고 각각의 값을 곱하면 합은 같지만 구성이 다른 순서쌍을 모두 구할 수 있다. 현재 left에서는 -5와 같은 수가 자기자신밖에 없으므로 1이고, right에서 5와 같은수가 3개 있으므로 1 * 3 = 3개의 순서쌍이 올바르게 구해짐을 알 수 있다.
# 코드
import sys # 입력부 n,s = map(int, sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) # 이분 분할 m = n//2 n = n - m # first : 왼쪽 Subset first = [0] * (1<<n) # 비트마스킹을 이용하여 Subset의 합을 담는다 for i in range(1<<n): for k in range(n): if (i&(1<<k)) > 0: first[i] += a[k] # second : 오른쪽 Subset second = [0]*(1<<m) for i in range(1<<m): for k in range(m): if (i&(1<<k)) > 0: second[i] += a[k+n] # first 오름차순 정렬, second 내림차순 정렬 first.sort() second.sort(reverse = True) # n, m = first의 길이, second의 길이 n = (1<<n) m = (1<<m) i = 0 j = 0 ans = 0 while i < n and j < m: # 같은 경우 if first[i] + second[j] == s: # i,j를 이동 c1 = 1 c2 = 1 i += 1 j += 1 # 예외 처리 while i < n and first[i] == first[i-1]: c1 += 1 i += 1 while j < m and second[j] == second[j-1]: c2 += 1 j += 1 # 전체 순서쌍 반영 ans += c1*c2 # 큰 경우 i만 이동 elif first[i] + second[j] < s: i += 1 # 작은 경우 j만 이동 else: j += 1 # s가 0인 경우 공집합의 경우를 빼줘야 하므로 1감소 if s == 0: ans -= 1 # 정답 출력 print(ans)
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 1248 "맞춰봐" (0) 2020.04.21 [Python 3] BOJ - 1238 "파티" (0) 2020.04.19 [Python 3] BOJ - 1107 "리모컨" (0) 2020.04.17 [Python 3] BOJ - 18117 "분수" (0) 2020.04.16 [Python 3] BOJ - 1080 "행렬" (0) 2020.04.14