프로그래머스 - 87946번: 피로도 [Java] 실패

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

프로그래머스

1. 코드

class Solution {
    static int answer = 0;
    static boolean[] check;
    public int solution(int k, int[][] dungeons) {
        check = new boolean[dungeons.length];
        DFS(k, dungeons, 0);
        return answer;
    }
    
    public void DFS(int k, int[][]d, int deep) {
        answer = Math.max(answer, deep);
        for(int i = 0; i < d.length; i++) {
            if(!check[i] && k >= d[i][0]) {
                check[i] = true;
                DFS(k - d[i][1], d, deep + 1);
                check[i] = false;
            }
        }
    }
}

2. 설명

dungeons의 행 길이는 8이기에 완전 탐색 방식으로 문제를 해결이 가능하다. 던전의 종류가 세가지라면 A▷B▷C, A▷C▷B, B▷A▷C, B▷C▷A, C▷A▷B, C▷B▷A 이렇게 총 6가지의 경우의 수를 모두 검사해야하는데 재귀와 반복문을 통해서 쉽게 구현이 가능하다.

3. 정리

1. 완전탐색에 대해서 잘 못하는 것을 느꼈다. 연습을 열심히 해야겠다.

4. 참고 글

[프로그래머스/java] 위클리 챌린지 87946 피로도

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges