백준 1182번 파이썬 문제풀이(대표값)

---

이 문제 쉬운 문제 치고 굉장히 고생했다. 또한 나의 dfs의 재귀개념에 대해서 다시 공부할 수 있는 좋은 계기가 되었다. 우선 음수가 끼여있으면 입력 받은 숫자들을 오름차순 정렬해서 만약 문제에서 요구하는 합보다 현재 합이 크다면 굳이 뒤의 원소들을 추가적으로 검사하지 않고 return하는 백트래킹 조건을 걸면 안된다. 왜냐하면 음수 끼리의 합은 더작아지기 때문이다. (예를들어 1 2 3 4 5 에서는 합이 5가 되는 경우를 찾을 경우 1 2 3 을 골랐다고 하였을때 이미 6이기 때문에 굳이 뒤에 원소들(4 , 5)을 검사할 필요 없이 바로 return 하고 2 부터 다시 검사를 하면 된다. 그러나 -7 -3 -1 5 8 에서 합이 -4가 되는 부분수열을 찾아야 하는데 -3은 이미 -4보다 크기 때문에 -1을 검사하지 않고 바로 return하게 되는 경우가 있다.)

 

1. 인자로 합을 바로 넘겨주어 구하는 방식

def dfs(depth, start, num):
    global count

    if 0 < depth <= N:

        if num == S:
            count += 1
        if depth == N:
            return

    for i in range(start, N):
        dfs(depth + 1, i + 1, num + arr[i])


N, S = map(int, input().split())
arr = list(map(int, input().split()))
count = 0

dfs(0, 0, 0)
print(count)

 

2. 리스트에 담아서 합을 구하는 방식

def dfs(depth, start):
    global count

    if 0 < depth <= N:
        if sum(result) == S:
            count += 1
        if depth == N:
            return

    for i in range(start, N):
        result.append(arr[i])
        dfs(depth + 1, i + 1)
        result.pop()


N, S = map(int, input().split())
arr = list(map(int, input().split()))
count = 0
result = []
dfs(0, 0)
print(count)

 

3. 정렬한 후 백트래킹 조건을 추가적으로 걸고 틀린 코드(음수가 있을 땐 불가능)

def dfs(depth, start):
    global count

    if N >= depth > 0:
        if sum(result) == S:
            count += 1
            return
    elif depth > N:
        return

    for i in range(start, N):
        result.append(arr[i])
        dfs(depth + 1, i + 1)
        result.pop()


N, S = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()  # 정렬한다.
count = 0
result = []
dfs(0, 0)
print(count)