[백준] 1182, 1208번(python 파이썬) - 부분수열의 합1, 2

문제링크(부분수열합1):https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

문제링크(부분수열합2):https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

문제 내용은 두 문제가 같기 때문에 부분수열의 합2로 올리겠다.

---

문제

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

입력

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

출력

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

 

 

 

 

 

 

풀이

---

이 문제는 하아...... 1, 2해결하는데 6시간이 걸렸다ㅋㅋㅋㅋㅋ

문제풀이 생각2시간 에러찾기 4시간......ㅜㅜㅜㅜㅜㅜㅜㅜ

울고싶다....

 

 

 

 

우선 이전에 포스팅했던 양팔저울문제를 풀고 이 문제의 easy버전이 1을 풀어보았다.

각각의 숫자에 대한 경우의 수는 2가지이다. 수가 있거나 없거나

그렇다면 이렇게 코드를 짤 수 가 있다.

종료 조건

 재귀가 n번 반복되는 경우(n은 숫자의 개수)

1.숫자 넣는 경우

2.숫자 넣지 않는 경우

 

이제는 뭔가 백트레킹이랑 다른알고리즘이랑 구분이 애매하다는 생각이 든다.

(아직 공부를 덜해서 그런 것 같다.)

 

이제 hard버전을 보자

 

hard버전은 시간제한이 1초이다. 당연히 easy버전처럼 풀면 시간초과가 난다. -> O(2**n)

그래서 처음에는 다음과 같은 생각을 했다. 

 

1. 주어진 부분을 2개로 나눈다. ->시간복잡도 O(2**n/2)로 바뀜(easy방식일때)

 

2.. combination을 활용해서 부분집합을 구한다. -> 시간복잡도: O(n! / r! / (n - r)!)

 

3. 이진 탐색을 사용해서 시간복잡도를 O(log n)으로 낮춘다.

 

여기서 시간을 오래쓴 부분은 bisect부분이다.

내가 알고 있던 이진탐색방식은 중복된 부분을 구할 수 없고 찾는 수가 해당리스트에 있는지만 탐색이 가능하다.

그래서 구글링을 해본 결과 같은 수가 있는 구간을 구할 수 있는 이진탐색방법이 있었다.

bisect함수를 import해서 쓸 수도 있다. 원리를 알 수 있는 링크를 달아놨다.

https://8iggy.tistory.com/124

이진 탐색(Binary Search) 알고리즘

 

근데 여기서도 문제가 있다.

 

bisect_left함수와 bisect_right함수에서 만약 찾는 값이 리스트의 끝에 있는 경우 right값과 left값이 동일하게 나오기 때문에

마지막에 위치한 정답을 찾을 수가 없다는 것이었다........

 

그래서 직접 구현을 해야된다고 생각을 했다... 너무 막막했다.

 

내가 구현한 방식은 다음과 같다.

 

1. 두 부분집합의 합을 정렬한다. 왼쪽 집합을 sub_1, 오른쪽 집합을 sub_2라고 하자

-> sub_1.sort(), sub_2.sort(reverse=True)

->하나를 반대로 정렬한 이유는 두개의 값을 합쳤을 때 만약 정답보다 작다면 sub_1의 index를 하나 더한 후 다시 계산

-> 정답보다 크다면 sub_2의 index를 하나 더한 후 다시 계산 과 같은 방식을 사용하기 위해서이다.

 

2. 만약 두 부분집합의 합이 정답일때

-> while을 이용해서 인덱스가 해당리스트의 길이보다 작은경우 and 다음 index가 현재index에 있는 수와 같은경우

-> 계속진행시킴 (index를 하나 더해줌)

r: 현재 right부분(sub_1) index

rs: r을 저장 후 index를 하나씩 늘려주어 r의 수와 rs의 수가 같다면 계속 진행

rs = r
while ls < left_len and sub_1[ls] == curr_left:
    ls += 1

물론 이 코드를 양쪽 다 진행시켜야 한다.

ex) 122225

       6541

이 경우에 정답이 6이라고 해보자 이 부분에서 위에있는줄을 l 아래있는줄을 r이라고 하면 l에서의 정답은 (2, 4)가

3개있는 것이다. r의 경우는 정답에서 같은 수가 (4, 2) 1개뿐이다. 따라서 

l, ls를 위의 정의에서 (left부분이라고 했을 때)

정답변수 = (ls-l) * (rs-r) 을 계산할 수 있다.

 

3. 부분집합에는 공집합이 항상 있다.

-> 만약 s가 0이라면 공집합끼리 선택했을때 정답으로 나온다. 하지만 그건 선택했다고 할 수 없기때문에 

-> s이 0이라면 정답수출력에 -1을 해주자

 

1과 2, 3부분을 활용해서 코드를 작성하면 정답이 나온다.

 

 

 

 

 

이 문제를 풀고 많이 부족하다는 것을 느꼈다..... 아직 갈길이 멀다...ㅜㅜ

에러고칠때 좀 많이 빡ㅊ....

 

 

암튼 오늘은 여기까지~~~~~~!

 

 

 

 

 

구현코드

---

easy버전

from sys import stdin
input = stdin.readline

n, s = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0

def dfs(num, tmp):
    global cnt

    if num >= n:
        return

    tmp += arr[num]
    if tmp == s:
        cnt += 1

    dfs(num+1, tmp) # 숫자를 고르는 경우
    dfs(num+1, tmp-arr[num]) # 아무것도 고르지 않는 경우

dfs(0, 0)
print(cnt)

hard버전

import itertools
from sys import stdin
input = stdin.readline

n, s = map(int, input().split())
arr = list(map(int, input().split()))
sub_1 = []
sub_2 = []
cnt = 0


for i in range(n//2 + 1):
    for j in itertools.combinations(arr[:n//2], i):
        sub_1.append(sum(j))
    left_len = len(sub_1)
    sub_1.sort()

for i in range(n - n//2 + 1):
    for j in itertools.combinations(arr[n//2:], i):
        sub_2.append(sum(j))
    right_len = len(sub_2)
    sub_2.sort(reverse=True)


l, r = 0, 0
cnt = 0

while l < left_len and r < right_len:
    curr_left, curr_right = sub_1[l], sub_2[r]
    curr_sum = sub_1[l] + sub_2[r]

    if curr_sum == s:
        ls = l
        rs = r
        while ls < left_len and sub_1[ls] == curr_left:
            ls += 1
        while rs < right_len and sub_2[rs] == curr_right:
            rs += 1
        cnt += (ls - l) * (rs - r)
        l, r = ls, rs
    elif curr_sum < s:
        l += 1
    elif curr_sum > s:
        r += 1


print(sub_1, sub_2)
print(cnt-1 if s == 0 else cnt)