[Python] 백준 1208

 

 

구글링이 잘 안돼서...직접 쓰는 리뷰 😅

 

 

 

 

1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다.

n개의 원소를 가진 수열의 부분 수열을 구하는 방법은 2**n 이라고 한다.

이 문제의 최대 범위는 n==40이므로 최악의 경우 2**40의 복잡도를 가지게된다.

그래서 이 문제는 리스트를 반으로 나눠 반에 해당하는 부분 수열을 구할 것이다. 그럼 최악의 경우 (2**20)*2이다.

(2**20)*2 = 2097152 VS 2**40 = 1099511627776 효율 ㅇㅈ?

 

나는 딕셔너리를 사용해서 부분 수열을 구했다. (이유는 뒤에)

key : 부분 수열의 합

value : 해당 부분 수열의 합이 나온 횟수

 

 

예제를 예로 들어 코드 설명을 하자면 우선 l=[-7,-3] r=[-2,5,8] 이다.

lsum과 rsum에 각각의 부분 수열의 합을 저장해준다.

해당 리스트를 가지고 two-pointer를 통해 부분 수열의 합을 구할것이다.

먼저 lsum과 rsum의 key값을 sort해서 저장한다. 그리고 다음과 같이 동작할 것이다.

l=0 (lsum에서 가장 작은 값부터) r=len(rkey)-1 (rsum에서 가장 큰 값부터)

✔ 왼쪽+오른쪽 > s ? r-=1 해서 숫자를 줄인다.

✔ 왼쪽+오른쪽 < s ? l+=1 해서 숫자를 키운다.

✔ 왼쪽+오른쪽 == s ? 만들 수 있는 합의 종류를 모두 추가한다. (value*value)

 

 

 

처음에 0의 value를 1로 지정해준 이유는 다음과 같다.

예를 들어 예제에서 찾고자하는 합이 5일 때 원소 5만 가지고 만들 수 있다.

하지만 0을 추가하지 않은 두 리스트의 합으로는 5를 구할 수 없다.

즉, 0은 해당 리스트에서 아무 숫자도 선택하지 않은 경우를 뜻한다.

 

딕셔너리를 사용한 이유는 다음과 같다.

예를 들어 수열 1 1 1 1에서 합이 2가 될 때를 찾고자 한다면

먼저 lsum=[0 1 1 2] rsum=[0 1 1 2]가 될 것이다. 이 때 처음 2가 되는 순간은 다음과 같다.

 

 

이때 l+=1할 것인가 r-=1 할 것인가?

고민하다가 그냥 counter를 통해 이런 경우를 없애 주고자 딕셔너리를 사용하였다!

 

 

마지막으로 반례가 있다. 구하고자 하는 합 s가 0인 경우이다.

처음 l,rsum에 초기화 해준 0=1은 아무것도 선택하지 않은 경우이다.

하지만 두 리스트에서 둘 다 아무것도 선택하지 않는 경우는 안된다. 부분수열의 크기가 양수라는 조건이 있기 때문이다.

그래서 마지막에 s==0이면 res-=1을 한다.

(구하고자하는 합이 0이 아닌경우에는 res에 0 0 인 경우가 추가되지 않기 때문에 상관없다.)

 

 

Result

import sys
from itertools import combinations
from collections import defaultdict

n,s=map(int,sys.stdin.readline().split())
m=list(map(int, sys.stdin.readline().split()))


l=m[:n//2]
r=m[n//2:]

lsum=defaultdict(int)
rsum=defaultdict(int)
lsum[0]=1
rsum[0]=1
for i in range(1,len(l)+1):
    for com in combinations(l,i):
        lsum[sum(com)]+=1

for i in range(1,len(r)+1):
    for com in combinations(r,i):
        rsum[sum(com)]+=1

lkey=sorted(lsum.keys())
rkey=sorted(rsum.keys())

res=0
l=0
r=len(rkey)-1
while l<len(lkey) and r>=0:
    if lkey[l]+rkey[r]==s:
        res+=(lsum[lkey[l]]*rsum[rkey[r]])
        l+=1
        r-=1
    elif lkey[l]+rkey[r]>s:
        r-=1
    else:
        l+=1

if s==0:
    res-=1
print(res)

 

 

나는 개객개개개어려웠다... 이렇게 고려해야 할게 많은 문제는 아직 너무 버겁다ㅜㅜ