[프로그래머스/JAVA] 위클리 챌린지 12주차(피로도)

 

코딩테스트 연습 - 12주차

 

 

---

 

 

• 풀이

 

처음엔 정렬한 후 풀어보려고했지만 입력값이 까다로워서 정확한 답을 구현할 수 없었습니다.

 

던전의 수가 최대 8개로 많지 않기때문에 완탐을 했습니다.

dfs 방식으로 완전 탐색 했습니다.

 

 

• 코드

 

import java.util.*;

class Solution {
    static boolean[] check;
    static int answer;
    
    public int solution(int k, int[][] dungeons) {
        check = new boolean[dungeons.length];
        answer = 0;
        
        for(int i = 0; i < dungeons.length; i++){
            if(dungeons[i][0] > k) continue;
            
            check[i] = true;
            dfs(k-dungeons[i][1], dungeons, 1);
            check[i] = false;
        }
        
        return answer;
    }
    
    private static void dfs(int k, int[][] dungeons, int count){
        answer = Math.max(answer, count);
        
       for(int i = 0; i < dungeons.length; i++){
            if(dungeons[i][0] > k || check[i]) continue;
            
            check[i] = true;
            dfs(k-dungeons[i][1], dungeons, count+1);
            check[i] = false;
        }
    }
}