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

문제

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

코딩테스트 연습 - 12주차

 

풀이

입장 피로도와 소모피로도 두 가지가 있는데 
만약 입장컷이 큰 순서대로 간다면 .. ? => 예제에서 3번째 던전을 못 돌기때문에 fail
그렇다고 작은 순서대로 간다면 .. ? => 입장컷이 큰 것이 나중에 나오면 못 돌기때문에 fail
결론 => 완전탐색

던전의 방문여부를 visit , 던전을 통과한 시점으로 남은 피로도를 tired , 던전 진행 갯수를 depth라고 하면
depth의 크기가 제일 큰 것이 정답.

class Solution {
    boolean[] visit;
    int[][] dungeons;
    int max=0;
    public int solution(int k, int[][] dungeons) {
        this.dungeons=dungeons;
        visit = new boolean[dungeons.length];
        for(int i=0;i<dungeons.length;i++) if(k>=dungeons[i][0]) dfs(i,k,1);
        return max;
    }
 
    private void dfs(int cur, int tired,int depth) {
        visit[cur]=true;
        tired -= dungeons[cur][1];
        for(int i=0;i<dungeons.length;i++) if(!visit[i] && dungeons[i][0] <= tired) dfs(i,tired,depth+1);
        max = Math.max(depth,max);
        visit[cur]=false;
    }
}