[프로그래머스] 피로도

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

모든 던전을 탐험할 수 있는 경우의 수를 보면서 최대로 탐험할 수 있는 던전 수를 확인해야한다.

 

단 두 가지 규칙이 있다.

• 현재 피로도가 던전의 최소 피로도보다 높아야 해당 던전에 들어갈 수 있다.
• 던전을 방문하면 현재 피로도에서 필요 피로도를 빼야한다.

따라서 던전을 탐험하다가 현재 피로도가 던전의 최소 피로도보다 낮으면 백트래킹 해야한다.

 

던전을 탐험하는 모든 경우를 확인하는 건 재귀를 통해 구현할 수 있다.

재귀를 통해 모든 경우의 수를 확인하다가 현재 피로도가 던전의 최소 피로도보다 낮은 경우가 발생하면 바로 백트래킹하면 된다.

그렇게 모든 경우의 수를 확인해 방문할 수 있는 최댓값을 구하면 된다.

 

코드로 보자

 

3. 내 코드

---

import java.util.*;
class Solution {
    
    private int[][] Dungeons;
    private static int max = 0;
    public int solution(int k, int[][] dungeons) {
        Dungeons = dungeons;
        cntDungeons(new ArrayList<>(), k);
        
        return max;
    }
    
    private void cntDungeons(List<Integer> list, int k) {
        max = Integer.max(max, list.size()); // 방문한 던전의 갯수와 최댓값을 비교해 크면 업데이트
        if(list.size() == Dungeons.length)
            return;
        
        for(int i = 0; i < Dungeons.length; i++) {
            
            List<Integer> newList = new ArrayList<>(list);
            
            // 해당 던전을 방문한적이 없고 해당 던전의 최소 피로도보다 현재 피로도가 크거나 같으면
            if(!newList.contains(i) && k >= Dungeons[i][0]) {
                
                newList.add(i); /// 해당 던전 방문처리
                cntDungeons(newList, k - Dungeons[i][1]); // 현재 피로도에서 필요 피로도를 빼서 재귀 호출
            }
            
            // 그렇지 않으면 백트래킹
        }
        
    }
    
}

시간 복잡도

• O(N!)

N개의 던전을 방문하는 경우의 수는 N*(N-1)*(N-2) *... * 1이므로 O(N!)이 된다.

하지만 백트래킹을 통해 중간중간 연산 횟수를 줄였으므로 실제 연산은 이보다 훨씬 줄어든다.

 

for(int i = 0; i < Dungeons.length; i++) {

    List<Integer> newList = new ArrayList<>(list);

    // 해당 던전을 방문한적이 없고 해당 던전의 최소 피로도보다 현재 피로도가 크거나 같으면
    if(!newList.contains(i) && k >= Dungeons[i][0]) {

        newList.add(i); /// 해당 던전 방문처리
        cntDungeons(newList, k - Dungeons[i][1]); // 현재 피로도에서 필요 피로도를 빼서 재귀 호출
    }

    // 그렇지 않으면 백트래킹
}

• 방문 여부를 체크하기 위해 리스트를 사용했다.

 

4. 피드백

---

• 방문하는 모든 경우의 수는 재귀를 통해 구현할 수 있다.
• 특정 상황이 발생하면 백트래킹해서 해당 케이스를 사전에 종료한다.