프로그래머스 lv2 - 피로도 (자바)

문제

---

프로그래머스 lv2 - 피로도

풀이

---

완전탐색 문제

• 주어진 던전 개수가 최대 8개이므로 던전의 순열을 구해도 최대 8!이므로 완전탐색이 가능하다.
• 구해진 각 순열마다 던전을 탐험하면서 탐험할 수 있는 던전의 개수를 체크한다.

코드

---

< 내 코드 >

import java.util.*;
class Solution {
    int[][] dungeons;
    int[] list;
    int answer;
    public int solution(int k, int[][] dungeons) {
        this.dungeons = dungeons;
        list = new int[dungeons.length];
        for (int i = 0; i < dungeons.length; i++)
            list[i] = i;

        makeP(0, k);
        return answer;
    }

    void makeP(int idx, int k) {
        if (idx == list.length) {
            int cnt = 0;
            for (int i : list) {
                if (k >= dungeons[i][0]) { // 던전 진입 가능
                    k -= dungeons[i][1];
                    cnt++;
                }
            }
            answer = Math.max(answer, cnt);
            return;
        }

        for (int i = idx; i < dungeons.length; i++) {
            swap(idx, i);
            makeP(idx + 1, k);
            swap(idx, i);
        }
    }

    void swap(int idx1, int idx2) {
        int temp = list[idx1];
        list[idx1] = list[idx2];
        list[idx2] = temp;
    }
}

< 더 효율적인 코드 - 프로그래머스 좋아요 가장 많이 받은 코드 >

 class Solution {
    int dfs(int k, int[][] dungeons) {
        int cnt = 0;
        for(int[] d : dungeons) {
            int a = d[0], b = d[1];
            if(a <= k) {
                d[0] = 9999;
                cnt = Math.max(1 + dfs(k - b, dungeons), cnt);
                d[0] = a;
            }
        }
        return cnt;
    }
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        return dfs(k, dungeons);
    }
}