백준 18429 근손실 (with Python)

어떤 문제?

제목에 적힌 문제이고, 완전 탐색으로 풀이가 가능한 문제입니다.

내가 작성한 Solution

재귀를 이용한 완전 탐색으로 풀었습니다.

문제에서 생각해볼 점

• 재귀 호출하는데, 중량이 500 미만인 경우는 더 이상 탐색할 필요가 없으므로 탐색 중단합니다. (Backtracking)

코드 구현

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

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

chk = [0]*N
result = 0

def f(k, weight):
    global result
	
    # Backtracking
    if weight < 0:
        return
    if k >= N:
        result += 1
        return

    for i in range(N):
        if chk[i] == 0:
            chk[i] = 1
            f(k+1, weight+kit[i]-K)
            chk[i] = 0
f(0, 0)

print(result)