백준 - 1182(부분 수열의 합, 파이썬)

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

문제 접근

• 문제를 보자마자 아 이거 재귀함수로 다 해보면 되겠는데? 라는 생각이 들었다.
• 재귀함수의 리턴하는 성질을 이용하면 모든 경우의 수를 구할 수 있다는건 코테 문제 쫌 풀어본 사람이면 알 것이다.
• 근데 뭐지..정답이 12퍼센트에서 틀렸습니다가 나왔다.

일단 정답 코드

n, s = map(int, input().split())
numbers = list(map(int, input().split()))
cnt = 0

def dfs(depth, temp):
    global cnt


    if depth >= n:
        return
    

    temp += numbers[depth]

    if temp == s:
        cnt += 1
    # 현재 정수에 다음 수를 더한 것    
    dfs(depth +1, temp)
    
    # 현재 정수에 다음 수를 더하지 않은 것(백트래킹)
    dfs(depth +1, temp -numbers[depth])


dfs(0,0)
print(cnt)

 

처음에 위의 코드에서

 dfs(depth +1, temp -numbers[depth])

위의 부분을 작성하지 않고

dfs(depth +1, temp + numbers[depth])

이런식으로 한번만 재귀를 시켜줬다. 예제 코드는 잘 통과했지만 앞서 말한대로 정답이 12퍼에서 틀렸습니다가 나왔다.

 

왜 틀렸던거지

사실 그냥 재귀함수 구현에 익숙하지 않아서 틀렸던거라지만 그러면 발전이 없으니 좀 더 디테일하게 왜 틀렸는지 알아보자 

틀렸던 코드(처음짠 코드)

n, s = map(int, input().split())
numbers = list(map(int, input().split()))
cnt = 0

def dfs(depth, temp):
    global cnt


    if depth >= n:
        return

    if temp == s:
        cnt += 1

    dfs(depth +1, temp +numbers[depth])


dfs(0,0)
print(cnt)

 

위처럼 구현할 경우 재귀 호출을 할 때마다 현재 합이 누적되어 가면서 모든 부분 집합을 탐색한다.

 

예를들어 n, s = 3, 4이고 numbers = [1,2,3]이라하면 위의 코드는 차례대로 누적해서 구하므로 2를 건너뛰고 1과3을 선택하지 못해 결과가 0이나오고 정답으로 제출한 코드는 모든 경우를 구해 결과가 1로 나온다.

 

한마디로 정답 코드는 중간 값을 뺀 경우도 생각해서 모든 경우를 다 구한 것이다.

 

 

P.S

비슷한 백트래킹 문제 풀어보면서 다시 해봐야겠다.