[JAVA] 프로그래머스 - 피로도

 

프로그래머스 고득점 알고리즘kit 완전탐색 lv.2 문제인 피로도 문제다.

각 던전에 입장할 수 있는 최소한의 피로도와 던전을 탐험했을 때 소모되는 피로도를

고려하여 최대한 많은 던전을 탐험하고 그때의 던전 수를 구하면 된다.

 

✅ 핵심 풀이

모든 경우의 수에 대해서 던전을 탐험하고 탐험이 완료된 뒤 탐험 횟수의 최대 값을 갱신해 주면 된다.

따라서 완전탐색을 이용하여 풀었고 탐험했던 던전을 중복하여 탐험하지 않기 위해 boolean 타입의

visit 배열을 사용했다.

하지만 간과한게 하나 있었으니, 처음에 현재 피로도가 최소 필요 피로도보다 작은 경우

해당 던전을 방문처리하고 continue로 넘어가도록 코드를 짰는데 테스트 케이스는 통과했으나 

다른 테스트 케이스에서 실패가 뜨고 말았다.

최소 필요 피로도를 만족하지 못한 경우, 방문 처리만 해줄게 아니라 탐험 횟수 증가와

피로도 감소 연산을하지 않고서 재귀 호출을 했어야 했다.

 

🚨 CODE

import java.util.*;

class Solution {
    static boolean[] visit;
	static int result = 0;
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        visit = new boolean[dungeons.length];
		solve(k, dungeons, 0, 0);
		answer = result;
        
        return answer;
    }
    public static void solve(int k, int[][] dungeons, int depth, int count) {
		// 모든 던전을 탐험했다면 최대 탐험 횟수 갱신
		if(depth == dungeons.length) {
			result = Math.max(result, count);
			return;
		}
		
		for(int i = 0; i<dungeons.length; i++) {
			if(visit[i]) // 이미 방문했던 던전이면 패스
				continue;
			int req = dungeons[i][0];
			int consum = dungeons[i][1];
			// 현재 피로도가 요구 피로도 보다 낮은 경우 패스
			if(k < req) {
				visit[i] = true;
				solve(k, dungeons, depth+1, count);
				visit[i] = false;
			}else {
				// 요구 피로도 만족 시
				visit[i] = true;
				solve(k-consum, dungeons, depth+1, count+1);
				visit[i] = false;
			}
		}
	}
}