[Java] 2021 위클리 챌린지 12주차 - 피로도

[Java] 2021 위클리 챌린지 12주차 - 피로도

던전의 개수가 8개로 수가 많지 않다.

던전을 탐험하는 경우의 수는 8! 인데, 이는 작은 숫자이므로 Brute force로 해결이 가능하다.

순열을 찾는 알고리즘은 back tracking을 사용할 수 있는데, 던전을 방문하고 함수를 탐색을 하고 탐색이 끝나면 방문 내역에서 지워주면 된다.

import java.util.HashSet; import java.util.Set; class Solution { Set visited = new HashSet<>(); int answer = 0; public String makeKey(int[] d){ return d[0] + "&" + d[1]; } public void solve(int k, int[][] dungeons, int depth){ int n = dungeons.length; answer = Math.max(depth, answer); for(int i = 0; i < n; i ++){ int[] d = dungeons[i]; String key = makeKey(d); if(!visited.contains(key) && k >= d[0]){ visited.add(key); solve(k - d[1], dungeons, depth + 1); visited.remove(key); } } } public int solution(int k, int[][] dungeons) { solve(k, dungeons, 0); return answer; } }

반응형

from http://blue-jay.tistory.com/89 by ccl(A) rewrite - 2021-10-26 21:27:53