[프로그래머스,Java] Level2: 피로도 (위클리 챌린지 12주차)

 

문제분석

RPG 게임에서나 보는 피로도 관련된 문제다.

 

던전을 도는 조건은 '최소 필요 피로도'를 넘겨야하고, 넘겼다면 '소모 피로도'를 깍아야한다.

 

아니.. 어느게임이 최소 필요 피로도가 있습니까.. 소모 피로도만 충족하면되지..

 

언뜻 보면 쉬워보인다. 

 

그냥.. 최소 필요 피로도가 큰 순서대로 피로도를 먼저 빼면 될것같다.

 

-> 하지만, 만약 [80,80] 이라면 첫번째 던전만 돌고, 2번 3번 던전을 못돈다.

-> 차라리, 첫번째 던전을 안돌고 2번 3번을 도는게 피로도 적으로 더 이득이다.

 

그러면.. 소모 피로도가 적은 순서대로 피로도를 먼저 빼면 되나..??

 

-> 이러면, 3번 2번 순서대로 던전을 돌텐데 그러면 1번던전을 못간다.

-> 모든던전을 도는방법 1, 3, 2로 도는방법이 실제로 있는데도 말이다.

 

 

결국에, 이 문제는 우선순위로는 못푼다. 

 

우선순위로 못풀면 어쩌겟나.. 완전탐색으로 모든경우를 찾아봐야한다.

 

제한사항을보니 던전갯수도 최대 8개다. 완전탐색을 돌리면 8!이니 그렇게 많은 연산은 안쓴다.

 

 

 

풀이과정

 

1.던전들의 순열을 구한다.

2.던전들을 도는 순번을 담은 output대로 피로도 계산을한뒤, 횟수를센다.

3.횟수들중에 Max값을 리턴한다.

 

문제풀이

import java.util.*;
class Solution {
    
int max=0;
    public int solution(int k, int[][] dungeons) {
        
        boolean[] visited = new boolean[dungeons.length];
        int[][] output = new int[dungeons.length][2];
        per(output,dungeons,visited,0,dungeons.length,k);
        
        return max;
    }
    
    public void per(int[][] output,int[][] dungeons,boolean[] visited,int depth,int r,int k){
        
        if(depth==r){
            calculate(output,k);
            return;
        }
        
        
        for(int i=0;i<dungeons.length;i++){
            if(!visited[i]){
                visited[i] =true;
                output[depth]=dungeons[i];
                per(output,dungeons,visited,depth+1,r,k);
                visited[i]=false;
            }
        }
    }
    
    public void calculate(int[][] output,int k){
        int temp=0;
        for(int i=0;i<output.length;i++){
            if(k>=output[i][0]){
                k-=output[i][1];
                temp++;
            }
            else{
                break;
            }
        }
        
    
        max=Math.max(max,temp);
    }
}