피로도_복습

2026.07.22

문제 풀이

나의 코드

---

소요 시간: 20분
시간 복잡도: $O(n!) (n = 던전 개수)$

---

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

AI 코드

---

시간 복잡도: $O(n!) (n = 던전 개수)$

---

코드 분석

전체적인 코드 구조는 거의 동일하고 가독성 측면에서 일부 변경되었음.

---

class Solution {
    static int answer = 0;
    static boolean[] visited;

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

    private void dfs(int k, int depth, int[][] dungeons) {
        answer = Math.max(answer, depth);
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && k >= dungeons[i][0]) {
                visited[i] = true;
                dfs(k - dungeons[i][1], depth + 1, dungeons);
                visited[i] = false;
            }
        }
    }
}

문제 풀이 후기

이 문제를 처음 풀었을 때에는 dfs에 대한 활용이 많이 부족했다.

복습을 하면서 아주 쉽게 문제를 해결했는데
이전보다 실력이 나아진 것은 분명하나,
문제 해결 방법을 외워서 푼 것 같아
다른 문제들도 계속 풀어보며 점점 고난이도의 문제들을 해결하는 것이
필요할 것 같다.

틀렸던 문제들에 대해 복습을 반복하며 내가 어떤 점이 부족했고 보완해야 하는가를 깨닫고, 정답률이 낮은 고난이도 문제들과 더불어
Level 3의 문제들을 도전해가는 방향으로 진행하면 실력 향상이 이루어질 것이다.