[백준][Python] 18429번 근손실

18429번: 근손실

 

 

코드

n,k = map(int,input().split())
n_list = list(map(int,input().split()))
visit = [False] * n
cnt = 0
ans = 0

def dfs(weight):
	global cnt, ans
	if weight < 500:
		return
	if cnt == n:
		ans += 1
		return
	
	for i in range(n):
		if visit[i] == False:
			visit[i] = True
			weight = weight - k + n_list[i]
			cnt += 1
			dfs(weight)
			visit[i] = False
			weight = weight + k - n_list[i]
			cnt -= 1

dfs(500)
print(ans)

 

설명

visit 리스트를 이용하여 이미 사용한 운동 키트인지 확인했다.

중량이 500 아래로 내려가면 바로 return을 해서 weight값과 cnt 값을 이전으로 돌려놓고, visit도 False로 바꿔줬다. 만약 500 아래로 내려가지 않고 모든 운동 키트를 사용했다면 cnt 값을 1 증가시켰다.