[백준 18429] 근손실 (python)

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

18429번: 근손실

근손실 문제

주어진 용량 키트를 사용하여 운동을 할 때, 근손실로 인한 중량이 500보다 작아지지 않게 할 수 있는 경우의 수를 모두 찾는 문제

백트래킹을 이용하여 해결 할 수 있었다.

📌 문제 접근 포인트

1. 근손실로 인한 중량이 500보다 작아지지 않게 하도록 경우의 수를 탐색해보자.
2. 매일같이 근손실이 일어나므로 K를 빼줄 수 있게 구성하고, 각 키트를 중복으로 선택하지 않도록 체크 해주면서 탐색하자.
3. 조건에 맞게 백트래킹을 구성하면 구현할 수 있다.

⚙️내가 푼 정답 코드

def find(x,n):
    global result
    if x < 500: # 500 보다 작아지면
        return # 끝
    if n == N: # 운동 일 다 채우며
        result += 1 # 홧수 증가
        return 
    x -= K  
    for i in range(N):
        if not visited[i]: # 사용하지 않았을 경우 탐색
            visited[i] = 1
            find(x + kit[i],n+1)
            visited[i] = 0

import sys
N, K = map(int, sys.stdin.readline().split())
kit = list(map(int,sys.stdin.readline().split()))
result = 0 
visited = [0]*N
find(500,0)
print(result)