프로그래머스(JAVA) - level2(피로도)

문제정리

현재 피로도를 k, 2차원 배열 dungeons에 최소 필요 피로도, 소모 피로도가 담긴 값을 주어진다.
유저가 탐험할 수 있는 최대 던전 수를 반환

 

처음 해결하려고 생각해본건.. 일단 소모 피로도를 정렬해서 작은 수를 대입, 던전을 도는 방법을 선택하려고 했다가 최소 피로도가 높아서 못들어가면 어쩌나 하는 고민이 또 생김.. 그렇다면 모든 조건을 대입해서 값을 내야할 것 같은데 어떻게..? 대입해야하는 걸까... ??

생각하다가.. 도저히 해결법을 생각해낼 수 없어 구글링해서 해결했다.. 내일 한번 더 풀어봐야지

최종코드

class Solution {
    private static int answer;
    private static boolean[] visit;

    public int solution(int k, int[][] dungeons) {
       int depth = 0;
       visit = new boolean[dungeons.length];

       dfs(depth, k, dungeons);

       return answer;
    }

    private  static  void dfs(int depth, int k, int[][] dungeons){
        for(int i = 0; i < dungeons.length; i++){
            if(!visit[i] && k >= dungeons[i][0]) { // 방문하지 않았고, 최소 피로도 조건 충족
                visit[i] = true; // 방문 처리
                dfs(depth + 1, k - dungeons[i][1], dungeons); // 피로도 감소 & 다음 탐색
                visit[i] = false; // 원상 복구 (백트래킹)
            }
        }

        answer = Math.max(answer,depth);
    }
}

 

이 방법을 보고 왜 for문인데 모든 경우를 탐색할 수 있는걸까..? 라는 생각이 들었는데, 각 dfs() 호출마다 for문이 실행되므로, 그때마다 새로운 던전을 선택할 수 있다!
재귀 호출 후 visit[i] = false;를 수행하여 던전을 취소하고 다른 경우를 탐색할 수 있다!!
이렇게 모든 경우를 탐색할 수 있음..

해결확인 후 다시 풀어봤을때 시간

 

 

내일 한번 더 풀어보자 !