프로그래머스 위클리 챌린지 12주차 - java

문제 설명

1. 피로도와 [필요피로도, 사용피로도]가 주어진다.

2. 던전을 도려면 필요피로도보다 피로도가 많아야 하고, 사용피로도는 그 던전을 돌면 소요된다.

3. 가장 많은 수의 던전을 도는 방법을 구하면 된다.

풀이 과정

// 마지막 위클리 챌린지이다. 그래서인지 굉장히 쉬운 문제로 장식했다.

// 매우 간단한 브루트포스 - DFS or BFS 문제이다.

 

 1. 모든 경우의 수를 탐색한다. 

 2. DFS를 돌면서 한번이라도 탐색한 곳은 다시 탐색하지 않고, 다른 모든 경우를 선택하여 진행한다.

 3. 현재 피로도보다 필요 피로도가 크면 돌 수 없다.

 4. 현재 피로도가 필요 피로도보다 많은 경우 방문하고, 이후 다시 해당 process를 반복한다.

 5. 이걸로 구해진 경우가 끝나면 다시 방문을 하지 않은 것으로 초기화시켜주면 된다.

코드

	class Solution {
	public static boolean check[];
	public static int ans = 0;
	public int solution(int k, int[][] dungeons) {
	check = new boolean[dungeons.length];
	dfs(k, dungeons, 0);
	return ans;
	}
	public static void dfs(int tired, int[][] dungeons, int cnt){
	for(int i=0; i<dungeons.length; i++){
	if(!check[i] && dungeons[i][0]<=tired){
	check[i] = true;
	dfs(tired-dungeons[i][1], dungeons, cnt+1);
	check[i] = false;
	}
	}
	ans = Math.max(ans, cnt);
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

 

위클리 챌린지 끝!!