백준 1182번(파이썬):부분수열의 합
백준 1182번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/1182
문제 내용
나의 풀이
from itertools import combinations
N,S=map(int,input().split())
s=list(map(int,input().split()))
count=0
def solve(cnt):
global count
if cnt==N+1:
print(count)
return
a=list(combinations(s,cnt))
for i in a:
sum=0
for j in i:
sum+=j
if sum==S:
count+=1
solve(cnt+1)
solve(1)
우선 1 ~ N 개의 부분 집합들을 combinations함수를 이용하여 차례로 증가시키면서 구하는 방법을 생각했다. 그 후, 재귀를 이용하여 N개의 부분 수열까지 파악하도록 한 후에 개수를 출력하도록 했다. 문제를 해결하긴 했지만 실행시간이 조금 오래 걸렸다…
코드 수정
from itertools import combinations
N,S=map(int,input().split())
s=list(map(int,input().split()))
count=0
for i in range(1,N+1):
a=combinations(s,i)
for j in a:
if sum(j)==S:
count+=1
print(count)
나의 풀이에서 불필요한 부분이 너무 많았다는 것을 깨달았다. sum 함수로 편하게 구할 수 있고, 반복문을 통해서 할 수 있는 것을 굳이 재귀적으로 함수를 계속 호출하면서 수행했다. 따라서 불필요한 요소들을 제거하고 다시 해결해 봤다.
다른 풀이
N,S=map(int,input().split())
s=list(map(int,input().split()))
count=0
def subset_sum(idx,sub_sum):
global count
if idx==N:
return
sub_sum+=s[idx]
if sub_sum == S:
count+= 1
#해당 s[idx]가 부분수열에 포함 될때
subset_sum(idx+1,sub_sum)
#해당 s[idx]가 부분수열에 포함 되지 않을 때
subset_sum(idx+1,sub_sum-s[idx])
subset_sum(0,0)
print(count)
문제의 알고리즘 분류가 백트래킹 및 브루트 포스이기 때문에 그에 해당하는 풀이를 참고했다…
부분 수열에 현재 요소의 포함 유무에 따라서 재귀함수를 호출하는 방식으로 해결하는 풀이다. 알고리즘 분류방식에 맞게 해결하도록 연습해야겠다.
