[프로그래머스][JAVA][Lv. 2] 피로도

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

import java.util.ArrayList;

class Solution {
    int answer = 0;
    
    public int solution(int k, int[][] dungeons) {
        ArrayList<int[]> dungeonList = new ArrayList<>();
        
        for (int[] dungeon : dungeons) dungeonList.add(dungeon);
        checkDungeons(k, dungeonList, 0);
        return answer;
    }
    
    public void checkDungeons(int k, ArrayList<int[]> dungeonList, int count) {
        for (int[] d : dungeonList) {
            if (k >= d[0]) {
                ArrayList<int[]> nextList = new ArrayList<>();
                
                for (int[] tempD : dungeonList)
                    if (tempD != d) nextList.add(tempD);
                checkDungeons(k - d[1], nextList, count + 1);
            }
        }
        answer = Math.max(count, answer);
    }
}

---

후기

처음에 어떻게 풀지 생각이 안 나서 조금 고민했다. 하필 카테고리가 보이는 문제여서 완전 탐색이 대놓고 보였다... 못 봤으면 조금 고생했을 것 같다.

처음에 생각한 것은 최소 필요 피로도나 소비 피로도 순으로 정렬하는 것이었는데 생각해보니 정렬을 해도 의미가 없는게 최소 필요 피로도 내림차순으로 정렬하면 앞의 피로도가 높고 뒤의 피로도가 적을 경우 던전을 많이 돌 수가 없다. 소비 필요도 오름차순으로 정렬도 최소 필요 피로도를 제대로 맞출 수 없기 때문에 모든 경우를 도는 방법밖에 없다. 그래서 재귀 호출로 완전 탐색을 구현했다. 그런데 이건 문제에서 던전이 최대 8개밖에 없다고 해서 괜찮지만 만약 던전 수가 1000000 정도 된다고 하면 다른 방법을 찾아야 할 것이다.