BOJ 18429 - 근손실 (Python)

S3, 백트래킹

풀이

• k를 언제 빼줘야 되나를 고민했었는데, 그냥 arr[i] 값을 더할 때 같이 빼주면 되었다.
• 백트래킹 도전기... 화이팅

from sys import stdin
n, k = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
visited = [0] * n

now = 500
cnt = 0

def dfs(depth):
    global cnt, now
    if depth == n:
        cnt += 1
    else:
        for i in range(n):
            if not visited[i]:
                visited[i] = 1

                if now + arr[i] - k >= 500:
                    now += arr[i] - k
                    dfs(depth + 1)
                    now -= arr[i] - k
                    visited[i] = 0
                else:
                    visited[i] = 0

dfs(0)
print(cnt)