백준 18429 근손실 / python

문제 : 18429

풀이 point

전형적인 백트래킹 문제이다. 1번부터 진행하여 가능한 모든 경우의 수를 보는데, 중량이 500 이상이 되지 못하면 그 경우의 수는 보지 않고 다른 경우의 수로 넘어간다.

아직 백트래킹을 잘 모른다면 N과 M문제 시리즈를 추천한다.

코드

#백준, 18429 근손실

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

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

caseSum = 0

visit = [False] * N

def back(depth, weight):
    global caseSum
    if depth == N:
        caseSum += 1
        return

    for i in range(N):
        if not visit[i]:
            stand = weight+fiteness[i]-K
            if  stand >= 500:
                visit[i] = True
                back(depth+1, stand)
                visit[i] = False

back(0, 500)

print(caseSum)