피로도

작성일: 2024-10-29

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

접근 방식

재귀 함수를 이용해서, 완전 탐색 구현

잘못된 접근

class Solution {
    static int answer = -1;
    static boolean visited[];
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        explore(k, dungeons, 0, 0);
        return answer;
    }

    private void explore(int k, int[][] dungeons, int cnt, int sum){
        if (cnt==dungeons.length){
            answer = Math.max(sum, answer);
            return;
        }

        for(int i=0; i<dungeons.length; i++){
            if(visited[i]) continue;
            if(dungeons[i][0] <= k) {
                visited[i] = true;
                explore(k-dungeons[i][1], dungeons, cnt+1, sum+1);
                visited[i] = false;
            }

        }
    }
}

주어진 테스트 케이스 한 개는 통과했지만, 제출 후에는 대부분의 테스트를 통과하지 못했다.

따라서, 80, [[40, 10], [30, 20], [40, 20], [10, 5]] 와 같은 테스트를 넣고 3이 도출되는지 확인해보았더니 그렇지 못했다.

이는 잘못된 기저 조건 설정 때문이었다. 현재 모든 던전을 탐험할 필요가 없다. 실제로 모든 던전을 탐험 할 수 없는 경우가 위의 예제이다.

따라서 기저 조건을 설정하는 것이 아니라, 모든 상황에서 현재의 던전 탐험 수가 최대인지를 판단에서 업데이트하는 것이 맞는 로직이다.

결과

소스 코드

class Solution {
    static int answer = -1;
    static boolean visited[];
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        explore(k, dungeons, 0, 0);
        return answer;
    }

    private void explore(int k, int[][] dungeons, int cnt, int sum){
        answer = Math.max(sum, answer);

        for(int i=0; i<dungeons.length; i++){
            if(visited[i]) continue;
            if(dungeons[i][0] <= k) {
                visited[i] = true;
                explore(k-dungeons[i][1], dungeons, cnt+1, sum+1);
                visited[i] = false;
            }

        }
    }
}

다른 접근 방식

방문 배열을 사용하지 않고, 탐험한 던전의 최소 필요도를 K값의 최대인 5001 이상으로 주는 방법이 있다. 해당 방법은 방문 배열 여부를 판단하지 않고, 필요로 하지 않기 때문에 공간 복잡도가 현재 코드보다는 줄어들 것으로 보인다.

class Solution {
    static int answer = -1;
    public int solution(int k, int[][] dungeons) {
        explore(k, dungeons, 0, 0);
        return answer;
    }

    private void explore(int k, int[][] dungeons, int cnt, int sum){
        answer = Math.max(sum, answer);

        for(int i=0; i<dungeons.length; i++){
            if(dungeons[i][0] <= k) {
                int tmp = dungeons[i][0];
                dungeons[i][0] = 5001;
                explore(k-dungeons[i][1], dungeons, cnt+1, sum+1);
                dungeons[i][0] = tmp;
            }

        }
    }
}

알게 된 점

없음.