[프로그래머스] LEVEL2 피로도 JAVA

피로도

문제링크

풀이

완전 탐색 관련 문제 였다.

1. 던전을 모든 순서대로 배열해서 문제를 푼다. (이때 permutation 활용했던 형식처럼 풀이하였다.)

2. 순서대로 선택할 때 다시 똑같은 던전을 선택하지 않도록 isSelected 배열을 생성하여 선택여부를 확인한다.

3. isSelected 배열을 통해 선택되지 않은 던전이 임시로 선택된 경우, 최소 필요 피로도 조건을 만족한다면 진짜로 선택하고 다음 던전을 선택한다.
   다음 던전 선택시 방문한 던전수를 +1 하고 (cnt+1), 방문 후 피로도를 감소 시킨 후 피로도를 전달한다. (k - dungeons[i][1])

4. 만약 임시로 선택된 던전이, 최소 필요 피로도 조건을 만족하지 않는 경우에는 던전 선택을 멈추고, 지금까지 방문한 던전수와 최대 방문 던전수(maxDungeon)을 비교한다.

5. 방문한 던전수가 N개가 되었을 경우도 마찬가지로, 지금까지 방문한 던전수와 최대 방문 던전수(maxDungeon)을 비교한다.
   (사실 최대 방문 횟수가 된다...)
   => 이 점을 활용해서 코드2에 아래와 같은 코드를 추가하여 실행시간과 메모리를 줄일 수 있었다. (가지치기)

if (maxDungeon == N){
    return;
}

코드1 (Time: 0.11 ms, Memory: 77.8 MB)

/*
최소 필요 피로도: 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도
소모 피로도: 던전을 탐험한 후 소모되는 피로도
*/
import java.util.Arrays;
class Solution {
    
    public int N, maxDungeon;
    public boolean[] isSelected;
    
    public int solution(int k, int[][] dungeons) {
        N = dungeons.length;
        maxDungeon = 0;
        isSelected = new boolean[N];
        
        dfs(0, k, dungeons);
        return maxDungeon;
    }
    
    public void dfs(int cnt, int k, int[][] dungeons) {
        if( cnt == N) {
            maxDungeon = Math.max(maxDungeon, cnt);
            return;
        }
        
        for (int i = 0; i < N; i++) {
            
            if (isSelected[i]) continue;
            
            if (k >= dungeons[i][0]) {
                isSelected[i] = true;
                dfs(cnt + 1, k - dungeons[i][1], dungeons);   
                isSelected[i] = false;
            }
            else {
                maxDungeon = Math.max(maxDungeon, cnt);
            }
            
        }
    }
}

코드2 (Time: 0.04 ms, Memory: 70.6 MB)

import java.util.Arrays;
class Solution {
    
    public int N, maxDungeon;
    public boolean[] isSelected;
    
    public int solution(int k, int[][] dungeons) {
        N = dungeons.length;
        maxDungeon = 0;
        isSelected = new boolean[N];
        
        dfs(0, k, dungeons);
        return maxDungeon;
    }
    
    public void dfs(int cnt, int k, int[][] dungeons) {
        if(cnt == N) {
            maxDungeon = N;
            return;
        }
        
        if (maxDungeon == N){
            return;
        }
        
        for (int i = 0; i < N; i++) {
            
            if (isSelected[i]) continue;
            
            if (k >= dungeons[i][0]) {
                isSelected[i] = true;
                dfs(cnt + 1, k - dungeons[i][1], dungeons);   
                isSelected[i] = false;
            }
            else {
                maxDungeon = Math.max(maxDungeon, cnt);
            }
            
        }
    }
}