[완전탐색] 피로도 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

[문제 간단 요약]

1. 하루에 최대 몇 개의 던전을 탐험할 수 있는지 구하는 문제

2. 각 던전마다 입장에 필요한 최소 피로도와 소모 피로도가 주어짐

3. 현재 피로도 k로, 주어진 순서에 상관 없이 던전을 탐험

[문제 해결 방안]

1. 던전 순서를 상관 없이 모든 경우의 수를 탐색 (dfs 활용)

2. 현재 피로도에서 탐험 가능성을 체크하여 문제 해결

 

[문제 해결 코드 - python]

def dfs(dungeons, k, cnt):
    global used
    max_cnt = cnt

    for i in range(len(dungeons)):
        if used[i] == 0 and k >= dungeons[i][0]:
            used[i] = 1
            result = dfs(dungeons, k - dungeons[i][1], cnt + 1)
            max_cnt = max(max_cnt, result)
            used[i] = 0
    
    return max_cnt

def solution(k, dungeons):
    global used
    used = [0] * len(dungeons)
    return dfs(dungeons, k, 0)

 

[문제 해결 코드 - javascript]

function dfs(dungeons, k, cnt) {
    if (k < 0) {
        li.push(cnt - 1)
        console.log(li)
        return 
    }
    for (let i = 0; i < dungeons.length; i ++) {
        if (used[i] === 0 && k >= dungeons[i][0]) {
            used[i] = 1
            dfs(dungeons, k-dungeons[i][1], cnt+1)
            used[i] = 0
        }
    }
    li.push(cnt)
    return li
}

function solution(k, dungeons) {
    let cnt = 0
    li = Array()
    used = Array.from({length: dungeons.length}, () => 0)
    return Math.max(...dfs(dungeons, k, cnt))
}