[BOJ] 18429 근손실 python

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

18429번: 근손실

풀이

백트래킹 문제라고 분류가 되어있었지만, 딱히 고려하고 풀진 않았다.

조건 중에

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

가 있어서 일일이 다 확인해도 된다고 생각하여 하나씩 다 순회해보기로 하였다.

 

처음 생각한 풀이는 itertools의 permutation으로 순열로 나열한 다음 각각 조건에 부합하는지 확인하면 되지만, 사용하지 않고 풀려고 했었다.

따라서 dfs를 이용하여 반복적으로 운동 키트의 원소들을 돌면서 마지막 원소(depth == N)까지 접근했을 때 답으로 세어 풀었다.

 

기존에 틀렸던 코드

import sys
input = sys.stdin.readline
N,K = map(int,input().split())
kit = list(map(int,input().split()))
visited = [False] * N
answer = 0
def dfs(depth,weight):
    global answer
    if depth == N:
        answer += 1
        return
    for i in range(N):
        if visited[i]:
            continue
        elif weight + kit[i] - K < 500: # 키트를 먹었을 때 조건 X
            return
        else: # 키트를 먹었을 때 조건 O
            visited[i] = True
            dfs(depth+1,weight + kit[i] - K)
            visited[i] = False
dfs(0,500)
print(answer)

처음에 구현했던 코드는 21%에서 틀렸다고 나와서 확인을 해보니

3 4
5 3 4

이 반례가 있어서 안 되었다.

이유는 위에서 동작하는 return이 재귀적으로 dfs를 호출했을 때 조건이 맞지 않는 경우와 답에 도달한 경우에만 다시 원래 함수로 돌아와야 하는 데, 마지막에 첫째날 4의 중량을 섭취했을 때에 접근할 수 없기 때문이다.

따라서 모든 순서에 대해 접근할 수 있도록 코드를 수정했다.

코드

import sys
input = sys.stdin.readline
N,K = map(int,input().split())
kit = list(map(int,input().split()))
visited = [False] * N
answer = 0
def dfs(depth,weight):
    global answer
    if depth == N:
        answer += 1
        return
    if weight < 500:
        return
    for i in range(N):
        if visited[i]:
            continue
        else:
            visited[i] = True
            dfs(depth+1,weight + kit[i] - K)
            visited[i] = False
dfs(0,500)
print(answer)