[프로그래머스-87946] 피로도 - 파이썬, 자바스크립트

 

문제

• 
   XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
   이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
  
  제한사항
  k는 1 이상 5,000 이하인 자연수입니다.
  dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  dungeons의 가로(열) 길이는 2 입니다.
  dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
  

  

  
  입출력 예 설명
  
  현재 피로도는 80입니다.
  만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면
•  현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.
  
  
  만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면
• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.
  따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.
  
  

 

해결 아이디어

문제 유형이 완전탐색이라, 우선 모든 순열에 대해 확인하는 DFS 방법을 이용해야 한다.

나는 모든 순열을 다 확인하면 시간복잡도 측면에서 불리한가라는 생각을 하였지만, 던전의 개수는 1이상 8이하이기 때문에, 최대 8개라고 해도 8! = 40320이므로 1초에 2000,0000번의 연산이 가능한 파이썬 입장에서는 매우 부담이 없는 연산량이다.

따라서 모든 순열을 탐색하며, 남은 피로도가 최소 요구 피로도 이상이면 진행하고, 진행 후에는 다시 백트래킹하여 다른 조합을 탐색하는 것이 핵심 로직이다.

 

해결코드 <Python>

1. 

from itertools import permutations

def solution(k, dungeons):
    max_clear = 0

    for perm in permutations(dungeons):
        cur_k = k
        cnt = 0
        for need, use in perm:
            if cur_k >= need:
                cur_k -= use
                cnt += 1
            else:
                break
        max_clear = max(max_clear, cnt)

    return max_clear

파이썬의 itertools 라이브러리를 사용하면 쉽게 조합을 구할 수 있다. 이렇게 구한 모든 조합에 대해, 탐험한 던전 수를 각각 구하고 가장 많은 던전을 탐험한 수를 반환한다.

 

2.

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0


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

 

이 방법은 라이브러리를 사용하지 않고 DFS로 접근하는 방법이다.

visited배열을 0으로 초기화하고, 방문했으면 1로 바꿔 방문하지 않은 던전만 탐험한다.

한 곳으로 깊게 갔는데 더 길이 없는경우(조건 만족 x / 더 이상 방문할 수 있는 던전이 없음) 탐색을 종료한다. 백트래킹을 통해 다시 직전 단계로 돌아와 , 이전에 방문했던 던전의 방문 여부를 다시 0으로 초기화(visited[j] = 0)하여 다른 경로에서 다시 탐색이 가능하도록 한다.

 

해결코드<JavaScript>

function solution(k, d) {
    const N = d.length
    const visited = new Array(N).fill(0)
    let ans = 0

    function dfs(k, cnt){
        ans = Math.max(cnt, ans)

        for (let j = 0; j < N; j++){
            if (k >= d[j][0] && !visited[j]){
                visited[j] = 1
                dfs(k - d[j][1], cnt + 1)
                visited[j] = 0
            }
        }
    }

    dfs(k, 0)
    return ans;
}

동일한 방법이지만, 더 간단하게 나타낼 수 있다.