Java 프로그래머스 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

문제 분류 : 코딩테스트 연습 > 완전탐색 > 피로도 

난이도 : 2

 

정답 코드 

백트래킹을 활용해서 풀었다.

import java.util.*;
class Solution {
    static int max;
    static int [][] d;
    static boolean [] visited;
    public int solution(int k, int[][] dungeons) {
        max = 0;
        d = dungeons;
        visited = new boolean[dungeons.length];
        BackTracking(k, 0);
        return max;
    }
    public static void BackTracking(int cur, int count){
        boolean flag = true;
        for(int i = 0; i < d.length; i++){
            if(!visited[i] && cur >= d[i][0]){
                flag = false;
                visited[i] = true;
                BackTracking(cur - d[i][1], count + 1);
                visited[i] = false;
            }
        }
        if(flag){
            max = Math.max(max, count);
        }
    }
}