💯Problem Solving
[BOJ] 1208 부분수열의 합 2
date
Aug 5, 2023
slug
boj-1208
author
status
Public
tags
Python
BOJ
summary
백준 1208번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Aug 23, 2023 10:35 AM
문제 링크
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
문제풀이
N개의 수열에서 부분수열을 구하는 방법은 모든 원소를 각각 순회하면서 구하는 것인데,
이는 N = 40 인경우 n^40의 시간복잡도가 요구되어 시간초과가 된다.
그래서 Meet in middle 알고리즘을 사용하여 배열을 2개로 쪼갠 후 각각 구한다음에 구하는 방법을 사용해야한다.
우선 부분 수열이란, 수열 {a,b,c,d}가 있으면, 공집합을 포함하여,
{a},{b}, …. {a,b,c},{a,b,d} … {a,b,c,d} 까지 원래 수열의 순서를 유지하면서 나열할 수 있는 모든 경우의 수를 구하는것으로
파이썬에서는
li = list() for i in range(len(arr)): li.extend(list(itertools.combination(arr, i)))
이런식으로 구할 수 있다.
meet in middle 알고리즘은
전체 배열을 반으로 나누는 것이다. (이게 끝..)
- 전체 배열을 반으로 나눠서
- 왼쪽과 오른쪽에 해당하는 부분수열을 모두 구하고
- a+b+c+d → S가 되게 하는것을 x+y → S가 되게끔 하는것이다.
문제에서 요구하는것은 S가 되게끔 하는것이므로
left 배열과, right 배열의 부분수열을 모두 구한후, 합을 key, 갯수를 value로 하는 defaultdict에 넣어서
left배열을 순회하며, 합의 key를 k라고 했을떄 S-k가 right 배열에 key로 있으면
그 값을 곱한 것을 count에 추가해주면 된다.
그리고 마지막으로 S=0일때는 왼쪽이 0, 오른쪽이 0인 공집합이 계산되므로 이것을 제거해주면 된다.
파이썬 문제풀이 코드
from itertools import combinations from collections import defaultdict, Counter N, S = map(int, input().split()) arr = list(map(int, input().split())) # print(arr) start = 0 end = len(arr) mid = len(arr) // 2 def get_all_combinations(start, end): dd = defaultdict(int) for i in range(0, end-start+2): # 모든 부분수열의 합을 구할 조합, 0,1,2 - 3,4 # 공집합을 구해야, 한쪽집합에서만 정답이나오는 경우를 구할 수 있음 li = combinations(arr[start:end+1], i) # 0인것은 없음 for item in map(sum , li): dd[item] += 1 return dd left_dict = get_all_combinations(start, mid) right_dict = get_all_combinations(mid+1, end) # print(left_dict, right_dict) count =0 for k, v in left_dict.items(): if S-k in right_dict: # 오른쪽 dict에 잇다면 count += v * right_dict[S-k] if S == 0: count -= 1 # S가 0인경우, 공집합과 공집합인 경우를 더하므로 print(count)
시간복잡도
- O(2 * n^20)
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.