백준 18429 : 근손실 (Python)

본문 링크

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

visit=[False]*(N)
Answer=0
def BackTracking(deep , total):
    global Answer
    if total<300:
        return

    if deep==N:
        Answer+=1
        return

    for i in range(N):
        if not visit[i]:
            visit[i]=True
            BackTracking(deep+1 , total+L[i]-K)
            visit[i]=False
BackTracking(1,300)

print(Answer)

📌 어떻게 접근할 것인가?

백트래킹을 사용해 접근했습니다.

문제에서 매일 $K$ 만큼 근 손실이 일어나고 리스트의 값만큼 운동을 해서 값이 증가합니다.

이때 근육량이 한번이라도 300미만으로 떨어지면 제외해야 합니다.

if total<300:
	return

위와 같은 조건을 사용하였습니다.

if deep==N:
	Answer+=1
	return

만약 총 $N$ 일동안 근육이 300 미만으로 한번도 떨어지지 않는다면 경우의 수를 하나 추가합니다.

for i in range(N):
	if not visit[i]:
		visit[i]=True
		BackTracking(deep+1 , total+L[i]-K)
		visit[i]=False

중복없고 순서는 상관없기 때문에 모든 리스트 값에 대해 반복문을 돌려주고
visit 배열을 통해 만약 방문하지 않은 지점이라면 방문 처리 후 재귀함수를 호출합니다.
이때 깊이를 1 추가하고 근육량은 기존의 값에다가 리스트 값을 더하고 $K$ 를 바로 빼준 값을 넣었습니다.

이후 백트래킹을 해야하기 때문에 함수 호출후에 다시 방문처리를 되돌려 놓아주었습니다.

BackTracking(1,300)
print(Answer)

깊이는 1부터 시작했고 처음 근육의 크기는 300 이므로 매개변수를 1 과 300으로 했습니다.
이후 Answer 을 출력합니다.