프로그래머스 lv2 피로도

문제 링크

피로도

풀이

• '던'이 생각나는 문제다.
• 두 가지 풀이 방법이 생각났는데, 한 가지는 '순열'로 조합을 만들어서 모든 경우의 수를 따져보며 가장 깊게 탐색이 가능한 경우를 따져보는 것이고, 하나는 dfs를 해보는 것이다.
• 당연하게도 둘 다 못짰다.
• 어딘가에서 힌트를 얻어서 겨우겨우 코드로 만들었다.

class Solution {
    public int answer = 0;
    
    public int solution(int k, int[][] dungeons) {
        dfs(k, 0, new boolean[dungeons.length], dungeons);
        return answer;
    }

    public void dfs(int k, int depth, boolean[] visited, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if(!visited[i] && dungeons[i][0] <= k){ // 방문하지 않았고, 해당 던전의 최소 필요 피로도가 남아있는 k보다 적을 때 연산을 진행한다.
                visited[i] = true;
                dfs(k - dungeons[i][1], depth + 1, visited, dungeons); // 현재 피로도는 지나간 던전의 소모 피로도를 빼주고, 그 다음에 depth를 늘린다.
                visited[i] = false;
            }
        }
        answer = Math.max(answer, depth); // 반복문이 끝나면, depth는 이번 경로에서는 몇 개의 던전을 탐색했는지가 된다.
    }
}

소감

• 언제쯤 나 스스로 문제를 파악하고 어떤걸 사용해야하는지, 그리고 그걸 코드로 딱딱 짜낼 수 있을까..