87946. 피로도

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java

제한사항

풀이

import java.util.*;

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

회고

입력값이 자연수이고, 값의 범위가 작아서 그리디 알고리즘을 예상했는데 생각보다 단순했다. dfs를 활용한 백트래킹을 통해 해결할 수 있었다. k가 최소 필요 소모도보다 작으면 가지치기를 했다.