[백준 18429번] 근손실 - 파이썬

https://www.acmicpc.net/problem/18429

💡문제 분석 요약

매일 중량이 K만큼 줄어들 때, 매일 다른 운동 키트를 사용하여 중량을 500 이상으로 유지시킬 수 있는 경우의 수를 구하여라.

 

💡알고리즘 설계

1. 운동키트에 들어있는 운동기구로 늘릴 수 있는 중량과 매일 줄어드는 중량을 입력받는다.

2. dfs를 이용해 가능한 운동 기구를 다양한 순서로 이용한다.

3. 중량이 500 이하인 경우 탐색을 중단한다.

 

💡코드

import sys
input = sys.stdin.readline

N, K=map(int, input().split())
kit=list(map(int, input().split()))
visited=[False]*(N)

weight=500
result=0

def search(count, weight):
    global result
    if weight<500:
        return
    if count >= N+1:
        result+=1
        return
    
    for i in range(N):
        if not visited[i]:
            visited[i]=True
            search(count+1, weight+kit[i]-K)
            visited[i]=False

search(1, 500)    
print(result)

 

💡 느낀점 or 기억할 정보

result를 global로 선언 해 함수 안에서도 사용할 수 있게 해야한다.

visited[i]를 True로 한 후, search 함수를 호출 한 후에는 다시 False로 바꿔야 한다.