[BOJ] 18429 - 근손실 (Python, JavaScript)

 

 

아이디어

 

DFS로 가능한 순열 순서를 탐색하되, 백트래킹으로 중간에 500 미만이 되는 순서는 더 탐색하지 않는다.

 

 

풀이 #1 (Python)

 

운동 키트 중량 증가량을 리스트 A에 저장하고, 방문 표시를 위해 리스트 visited를 생성한 후 함수 dfs를 호출한다.

 

함수 dfs에서는 사용하지 않은 운동 키트들에 대해 visited에 표시한 후, 재귀 호출로 중량 total을 갱신하며 탐색해 나간다.

중간에 중량이 500 미만이 되면 현재 탐색을 종료하고 되돌아가고, 운동 일수 day가 N이 되면 결과값 res를 1 증가시킨다.

 

def dfs(day, total):
    global res
    if total < 500:
        return
    if day >= N:
        res += 1
        return
    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1
            dfs(day+1, total+A[i]-K)
            visited[i] = 0

N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [0]*N
res = 0
dfs(0, 500)
print(res)

 

 

 

풀이 #2 (Python)

 

풀이 #1에서 매일 중량이 K만큼 감소하더라도 마지막 날까지 500 미만이 되지 않는 경우를 백트래킹으로 처리한다.

 

함수 dfs에서 현재 중량에서 남은 일수에 K를 곱한 값을 빼도 500 이상인 경우,

남은 일수에 대해서는 순열로 가능한 경우의 수(남은 일수가 n일 때 n!)를 temp에 계산하여 결과값 res에 더한다.

만약 day가 N이 되었을 때는 for문이 실행되지 않아 temp에 저장된 1을 그대로 더한다.

 

def dfs(day, total):
    global res
    if total < 500:
        return
    if total-(N-day)*K >= 500:
        temp = 1
        for i in range(1, N-day+1):
            temp *= i
        res += temp
        return
    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1
            dfs(day+1, total+A[i]-K)
            visited[i] = 0

N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [0]*N
res = 0
dfs(0, 500)
print(res)

 

 

 

풀이 #3 (JavaScript)

 

풀이 #2와 같은 방식으로 동작하며, 함수 dfs 내에서 global.res로 결과값 res의 전역 변수 선언을 할 수 있었다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function dfs(day, total) {
    global.res;
    if (total < 500) return
    if (total-(N-day)*K >= 500) {
        let temp = 1;
        for (let i=1; i<N-day+1; i++) temp *= i;
        res += temp;
        return
    }
    for (let i=0; i<N; i++) {
        if (visited[i] === 0) {
            visited[i] = 1;
            dfs(day+1, total+A[i]-K);
            visited[i] = 0;
        }
    }
}

const [N, K] = input[0].split(' ').map(Number);
const A = input[1].split(' ').map(Number);
let visited = Array(N).fill(0);
let res = 0;
dfs(0, 500);
console.log(res);