백준 알고리즘 1182번: 부분수열의 합 (Python)

문제 정보

---

 

 

1182번: 부분수열의 합

 

 

핵심

---

풀이과정은 크게보면 두가지가 있는것 같다

첫번째는 정수 배열을 두개로 나눠서 백트래킹

두번째는 안나누고 한 배열로 백트래킹

확실히 정수 배열을 두개로 나누고, 백트래킹을 한 첫번째 풀이가 더욱 간단하고 실행시간도 짧았다

하지만 첫번째 풀이는 아직까지 완벽하게 이해하기 힘들었고, 두번째 풀이는 내가 직접 풀이했기 때문에 설명할 수 있을것 같다.

 

그냥 사실 간단한 문제이다. 중복을 고려하지 않은 조합을 찾는 것이지만, 이는 총 2^n-1 번의 경우의 수가 발생한다.

여기에서 정수의 개수는 20으로 제한되어 있기 때문에 최대 경우의 수는 1,048,576(2^20) - 1이 되겠다

 

 

풀이

---

import sys
input = sys.stdin.readline

N, S = map(int, input().strip().split())
numbers = list(map(int, input().strip().split()))
result = 0

def dfs(startidx, sums):
    sums += numbers[startidx]
    if sums == S:
        global result
        result += 1
    for idx in range(startidx+1, N):
        dfs(idx, sums)

for i in range(N):
    dfs(i, 0)

print(result)

시작 인덱스는 총 N개이고, 중복을 허용하지 않게 집합을 구성하면서 sum을 더해나가면 된다

sums가 S가 되면 result 변수의 값을 1씩 올려주는 방식으로 카운팅 해준다

이 풀이는 살짝 보완해 보자면

 

# 다른사람 풀이 (https://seongonion.tistory.com/98)

import sys
input = sys.stdin.readline
n, s = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0

def subset_sum(idx, sub_sum):
    global cnt

    if idx >= n:
        return

    sub_sum += arr[idx]

    if sub_sum == s:
        cnt += 1
    
    subset_sum(idx+1, sub_sum)
    subset_sum(idx+1, sub_sum - arr[idx])

subset_sum(0, 0)
print(cnt)

 

 

if idx >= n:
        return

해당 조건을 추가해준 후

    subset_sum(idx+1, sub_sum)
    subset_sum(idx+1, sub_sum - arr[idx])

이런식으로 재귀 호출을 실시해주면 된다

이유는 자기자신을 포함하거나, 포함하지 않거나 두개의 경우의 수가 존재하기 때문이다

 

 

고찰

---

사실 간단한 문제였지만, 될까 안될까를 자꾸 고민하다가 조금 시간이 소요되었던 것 같다

처음에는 depth를 사용하다가 나중에 sum을 조건으로 두었는데 이게 한수 였던것 같다

 

참고

---

GitHub - dduneon/CodingTestPy