백준 문제 풀이

18429 근손실

문제

웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다.

다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 수 있다. 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가하게 된다. 이 때 몇몇 운동 키트들의 중량 증가량이 같을 수 있으나, 서로 다른 운동 키트로 간주한다. 각각의 운동 키트는 N일 동안 한 번씩만 사용할 수 있다.

대학원생은 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고자 한다. 1일차부터 N일차까지의 모든 기간동안, 어떤 시점에서라도 중량이 500보다 작아지지 않도록 해야 한다.

예를 들어 N=3, K=4일 때, 각 운동 키트의 중량 증가량이 다음과 같다고 가정하자.

이 때 1번, 3번, 2번 순서대로 운동 키트를 적용한다고 해보자. 이 경우 운동 1일차에 대학원생은 중량이 3만큼 증가하지만 그와 동시에 하루에 중량이 4만큼 감소하기 때문에, 1일이 지난 이후에 중량은 499가 된다. 따라서 조건을 만족하지 못한다.

반면에 3번, 1번, 2번 순서대로 운동 키트를 적용한다고 해보자. 그러면 1일차부터 운동을 모두 마친 날까지의 모든 시점에 대하여 항상 중량이 500이상이 된다.

N개의 운동 키트에 대한 정보가 주어졌을 때, N일간 하루에 1개씩의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력하는 프로그램을 작성하시오.

위 예시에서는 모든 경우 중에서 총 4가지 경우가 조건을 만족한다.

입력

첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50) 둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50)

출력

N일 동안 N개의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력한다.

코드

N,K=map(int,input().split())
kit=[-1]+list(map(int,input().split()))
way=0
use=[1,-1]
visited=[-1 for _ in range(N+1)]
def dfs(day,num,weight):
    global way
    if day>N:
        return 
    if weight-K+kit[num]>=500:
        weight+=kit[num]-K
        visited[num]=1
        for j in range(2):
            if j==0:
                k=num+1
                while(k<=N):
                    if k!=num+1:
                        newnum=newnum+use[j]
                    else:
                        newnum=num+use[j]
                    if 0<newnum<=N and visited[newnum]!=1:
                        dfs(day+1,newnum,weight)
                        visited[newnum]=-1
                    elif day==N:
                        way+=1
                        return
                    k+=1
            elif j==1:
                k=num-1
                while(0<k):
                    if k!=num-1:
                        newnum=newnum+use[j]
                    else:
                        newnum=num+use[j]
                    if 0<newnum<=N and visited[newnum]!=1:
                        dfs(day+1,newnum,weight)
                        visited[newnum]=-1
                    elif day==N:
                        way+=1
                        return
                    k-=1

for i in range(1,N+1):
    newnum=-1
    dfs(1,i,500)
    visited[i]=-1
print(way)

풀이

알고리즘 분류가 브루트포스 알고리즘, 백트래킹으로 적혀있는 문제를 어려워했는데 드디어 풀어냈다!

브루트포스 문제이므로 모든 경우의 수를 다 체크해봐야 한다. 그래서 첫번째 기구부터 마지막 기구까지 차례대로 시작지점으로 설정해서, dfs방식으로 풀어냈다. 뻗어져나갔다가 조건에 맞지 않으면 돌아오는 방식으로 풀었고, 돌아오게 되는 경우에는 visited를 방문하기 전의 값으로 돌려놓고 다음 경로에서 방문했을 때 혼란이 없도록 만들었다.

계속 에러는 뜨지 않는데 값이 달라서 뭐가 문제인지 확인했더니, 두가지 이유를 찾을 수 있었다. 첫번째로 경로를 찾으면 카운트해주는 way 변수의 값이 변하지 않고 있었다. 이 문제는 global 키워드를 사용해서 해결할 수 있었다. way 변수는 전역 변수로, 함수 밖에서 선언되었다. 파이썬에서 함수 안에서 선언한 변수는 함수를 벗어나면 영향력이 없어지기 때문에 전역 변수의 값을 함수 안에서 변경하려면 global 키워드를 사용해야 한다. 두번째 문제는 기구의 사용 여부를 표시하는 visited 리스트의 값에 있었다. 함수에서 빠져나온 후에는 이전에 체크해뒀던 방문 여부를 해제해야 하는데 여전히 방문한 상태의 값을 가지고 있어서 제대로 탐색이 되지 않았다.

중복되는 코드도 있고 개선해야할 부분이 아직 있지만 우선 어려워했던 알고리즘인 브루트포스를 성공해냈다는게 너무 뿌듯하다!!