[프로그래머스(Programmers)][자바(java)] (Lv2) 12주차 - 피로도 <위클리 챌린지>

 

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

코딩테스트 연습 - 12주차

 

문제 풀이

 

*  완전 탐색

public class Solution {

	int n, a[], ds[][], ans_max;
	boolean v[];

	public void perm(int j, int k) {
		if (j == n) {
        	int ans = 0, d[];
			for (int i = 0; i < n; ++i) {
				d = ds[a[i]];
				if (k < d[0]) break;
				ans++;
				k -= d[1];
			}
			ans_max = ans_max < ans ? ans : ans_max;
		}
		for (int i = 0; i < n; ++i) {
			if (!v[i]) {
				v[i] = true;
				a[j] = i;
				perm(j + 1, k);
				v[i] = false;
			}
		}
	}

	public int solution(int k, int[][] dungeons) {
		n = dungeons.length;
		a = new int[n];
		v = new boolean[n];
		ds = dungeons;
		ans_max = 0;
		perm(0, k);
		return ans_max;
	}
}

던전의 개수가 최대 8개 이므로, 완전 탐색 수행 가능

 

*  DFS

public class Solution {

	int n, ds[][], ans;
	boolean v[];

	public void dfs(int k, int a) {
		int d[];
		for (int i = 0; i < n; ++i) {
			d = ds[i];
			if (!v[i] && d[0] <= k) {
				v[i] = true;
				dfs(k - d[1], a + 1);
				v[i] = false;
			}
		}
		ans = Math.max(a, ans);
	}

	public int solution(int k, int[][] dungeons) {
		n = dungeons.length;
		ds = dungeons;
		ans = 0;
		v = new boolean[n];
		dfs(k, 0);
		return ans;
	}
}