[백준] 1182번, 1208번: 부분수열의 합 1,2 파이썬 풀이

사용한 기술 스택들:  

 

오늘은 1182번과 1208번에 있는 부분 수열의 합 1,2를 풀어보겠다. 비트 마스킹을 이용한 브루트 포스 풀이와 dictionary를 사용해서 시간 복잡도를 √ 만큼 줄여주는 풀이를 해볼 것이다.

 

1182번: 부분수열의 합 (acmicpc.net)

1182번: 부분수열의 합

1208번: 부분수열의 합 2 (acmicpc.net)

1208번: 부분수열의 합 2

 

 

1182번: 부분수열의 합

코드

import sys

input = sys.stdin.readline
n,s=map(int,input().split())
arr=list(map(int,input().split()))
high=1<<n
count=0
for i in range(1,high):
    poss=("{:0"+str(n)+"b}").format(i)
    add=0
    for j in range(n):
        if poss[j]=="1":
            add+=arr[j]
    if add==s:
        count+=1
print(count)

설명

코드는 간단하다. 총 부분 수열의 개수는 2^n이고, n은 20이 최대이기 때문에 2^20=1048576 즉 충분히 돌아갈 수 있다. 비트 마스킹으로 모든 조합을 1부터 2^n-1까지 돌면서 만들어주면 된다. 여기서 1부터 시작하는 이유는 0일 때는 poss 가 00000 이런 식으로 될 텐데, 문제에서는 "크기가 양수인 부분 수열 중에서"라고 하기 때문에 공집합은 빼준다.

 

이미 알겠지만 이건 2**n과 동일하다.

high=1<<n

여기선 https://stackoverflow.com/questions/16926130/convert-to-binary-and-keep-leading-zeros에서 찾은 방법인데 파이썬에서 bin() 사용할 때 앞에 있는 0b를 없애주고 자릿수가 n만큼 생기게 해 준다. 만약에 bin(1)을 했다면 0b1이 나와서 비트 마스킹 하기가 애매해졌지만 여기서는 n=6이면 그냥 000001처럼 나타나게 도와준다. 

poss=("{:0"+str(n)+"b}").format(i)

poss의 각 자리에는 0이나 1이 있고 그 뜻은 poss [j]는 1일 때 arr [j]를 더해주고 0이면 더하지 않는다고 나타내는 것이다. 만약에 이번에 더해야 할 수가 2번째 3번째 5번째라면 01101 이런 식으로 나타내 준다. 만약에 add에 있는 부분 수열의 합이 s와 같아지면 count를 하나 올려주면 된다.

for j in range(n):
    if poss[j]=="1":
        add+=arr[j]
if add==s:
    count+=1

 

사실은 비트 마스킹을 안쓰고 그냥 다른방식으로 브루트포스를 하면 되지만(itertools) 이렇게 풀시에는 더 빠른 풀이가 가능하기 때문에 되도록이면 비트마스킹을 적용하려고 노력 중이다. 위에서 사용한 모든 경우 나타내는 format trick 같은 건 나중에도 유용하게 사용 가능하기 때문에 기억해두자.

 

1208번: 부분수열의 합 2

코드

import sys
from collections import defaultdict

input = sys.stdin.readline
n,s=map(int,input().split())
arr=list(map(int,input().split()))
half=n//2
other_half=n-half
count=0
sums=defaultdict(int)
for i in range(1<<half):
    poss=("{:0"+str(half)+"b}").format(i)
    add=0
    for j in range(half):
        if poss[j]=="1":
            add+=arr[j]
    sums[add]+=1
for i in range(1<<other_half):
    poss=("{:0"+str(other_half)+"b}").format(i)
    add=0
    for j in range(other_half):
        if poss[j]=="1":
            add+=arr[j+half]
    if s-add in sums:
        count+=sums[s-add]
print(count if s!=0 else count-1)

설명

이번은 n제한이 40이기 때문에 2^40=1099511627776 즉 1초에 돌아가기는 브루트포스 방식으로는 안된다. 그렇다면 문자열을 반으로 나누어주고 앞에 반쪽 문자열을 1182번처럼 계산한뒤, defaultdict에 저장하고 나머지 반쪽을 다시 똑같이 비교해서 부분수열 두개가 더해져서 s가 나오는지 확인하면 이게 2^(n/2) 풀이이다.

 

그럼 누군가는 궁금할수도 있다. 왜 굳이 dict를 안쓰고 defaultdict를 사용하는지 말이다. 만약에 밑에처럼 해준다면, key 값이 dictionary 안에 존재하지 않더라도 키를 지정해줄때 0을 기본 value 값으로 정해준다. 

sums=defaultdict(int)

나중에는 add가 dictionary에 없으면 생성해서 1을 더하는것보다 이렇게 간단하게 부분수열의 합들의 빈도를 저장할수 있다. 주석처리된 코드와 그냥 코드의 차이를 비교해보자.

sums[add]+=1

# if add in sums:
#	sums[add]+=1
# else:
# 	sums[add]=1

첫번째를 sums에 저장하고 반 두번째에 돌린때는 똑같이 하다가 여기서 sums defaultdict에 두번째 add에 대응하는 key,value pair가 있는지 확인하고 만약에 1개 이상 있다면 그 만큼을 count 해준다. 아까전에 말했듯이 sums에는 빈도가 저장되어 있었고, 그 빈도가 2 이상이라면 그 합이 2번 이상 나왔다는 말이다.

if s-add in sums:
    count+=sums[s-add]

여기서는 전 문제와 달리 range를 0부터 했기 때문에 공집합이 첫번째와 두번째가 하나씩 있다(전처럼 안해주는 이유는 둘중에 하나만 쓰고도 s가 만들어지면 0을 그 다른 걸로 설정해야 작동하기 때문이다). 그렇기 때문에 만약에 s=0라면 1을 빼서 출력해주자. 

print(count if s!=0 else count-1)

 

 

소스코드

baekjoonProblems/부분수열의_합.py at main · LimePencil/baekjoonProblems (github.com)

GitHub - LimePencil/baekjoonProblems: 백준 코딩문제 자바&파이썬 해답

baekjoonProblems/부분수열의_합_2.py at main · LimePencil/baekjoonProblems (github.com)

GitHub - LimePencil/baekjoonProblems: 백준 코딩문제 자바&파이썬 해답