[DFS] 백준 1182번 부분수열의 합 - Python 파이썬

 

 

생각하기

부분 수열을 만들 수 있는 모든 경우를 다 탐색해야 하는 브루트포스 문제이다. 

모든 경우를 탐색하면서 S가 될 때를 판단해야 하므로 반복문을 통해 하나씩 하는 건 말이 안된다

DFS를 사용해서 내려가면서 S와 비교를 하면서 개수를 카운트해야겠다고 생각했다

부분수열은 순서는 신경쓰지 않으니

DFS의 전체적인 로직은 시작하는 숫자를 Data의 Idx에따라 계속 바꾸어 나가자는 것!

 

구현하기

• answer 변수를 전역에 선언, 재귀적으로 DFS를 돌면서 answer을 쌓아갈 예정
• sum은 매번 DFS를 새로 시작할 때, 시작 포인트에서 첫 숫자로 초기화해준다
• 각 DFS는 recursive 하게 돌면서 자신이 쌓은 answer을 반환

DFS 메서드 구성

1. sum이 S와 같은 경우
2. idx가 마지막 idx인경우 (depth 가 마지막인 경우)
3. 다음 IDX로 탐색해야 하는 경우

예외 처리

첫 숫자가 data배열의 마지막 숫자일 때, Dfs를 하면 index초과 오류가 발생한다 -> 첫 숫자가 data배열일때, dfs안하도록 처리

부분수열에 숫자가 하나만 있는 경우도 처리해주어야함

import sys
input = sys.stdin.readline

N, S = map(int, input().split())

data = list(map(int, input().split()))

answer = 0


def dfs(idx, sum, answer):
    sum += data[idx]
    if sum == S: 
        answer += 1

    if idx == N-1:
        return answer
    
    for i in range(idx+1, N):
        answer = dfs(i, sum, answer)
    return answer
    
        

for i in range(0, N):
    sum = data[i]
    if sum == S :
        answer+=1
    if i != N-1:
        for j in range(i+1, N):
            answer = dfs(j, sum, answer)


print(answer)

 

 

다른 방법 

백준 강의를 듣고 다르게 푸는 방법도 있어서 구현해보았다

 

예외 처리

S==0 인데 집합에 아무것도 포함이 안된 경우, 이 또한 answer에 카운트 될 수 있다.

따라서 S==0인 경우 answer에서 1을 빼주어야 함

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import sys
input = sys.stdin.readline

N, S = map(int, input().split())

data = list(map(int, input().split()))

answer = 0

###방법 2####
def search(idx, sum):
    global answer
    if idx == N:
        if sum == S : 
            answer += 1
        return
    
    search(idx+1, sum+data[idx])
    search(idx+1, sum)

search(0, 0)

# S == 0인 경우 
if S == 0:
    answer -= 1

print(answer)