참고
문제해설
문제 로직고민
NOTE
•
이 유형은 브루트포스말고 정렬로도 풀 수 있다고 판단한다.
◦
던전을 필요피로도 → 소모피로도 순으로 정렬하고, 탐험이 가능할때까지 순차순회한다.
◦
물론 던전의 개수가 8개라서 브루트 포스로도 푸는 방식도 괜찮을것 같다.
•
위의 방식대로 진행했더니 반례가 너무 많이 생겼다.
◦
소모 피로도 순으로 우선순위를 바꿀까 고민했지만 이 방식 역시 반례가 생긴다.
◦
단순한 브루트포스로 풀이를 바꾼다.
작성코드
NOTE
import java.util.*;
class Solution {
int time;
int[][] dungeons;
boolean[] visited;
public int solution(int k, int[][] dungeons) {
this.time = 0;
this.dungeons = dungeons;
this.visited = new boolean[dungeons.length];
dfs(0, k);
return time;
}
public void dfs(int step, int hp){
time = Math.max(time, step);
for(int i =0; i<visited.length; i++){
if(!visited[i] && hp >= dungeons[i][0]){
visited[i] = true;
dfs(step + 1, hp - dungeons[i][1]);
visited[i] = false;
}
}
}
}
Java
복사
DFS 탐색이라 Stack으로 한번 해볼려했는데, Stack의 경우 시작던전을 지정해줘야 해서 재귀로 변경했다.
다른사람 풀이
NOTE
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);
}
}
Java
복사
가장 평가가 좋은 코드
•
내가 작성한 코드와 크게 다를게 없는것 같다.