https://programmers.co.kr/learn/courses/30/lessons/87946
풀이
Parameter
유저의 현재 피로도 iny k 1 <= k <= 5000
2차원 int 배열 dungeons 2 x 1~8
최소 필요 피로도, 소모 피로도
각 던전별 "최소 필요 피로도"
각 던전별 "소모 피로도"
1 <= 최소 필요 피로도 >= 소모 피로도 <= 1000
Return
유저가 탐험할 수 있는 최대 던전 수 int answer
Example
k dungeons result
80 [[80,20],[50,40],[30,10]] 3
PseudoCode
방문 배열 visited와 초기 답 변수 answer = -1 을 정의한다.
DFS를 실행한다.
DFS(던전 배열, 현재 피로도, 현재 거쳐온 던전 수)
조건에 해당하는 만큼 던전을 돌면서, 방문할 수 있는 던전의 개수 answer의 최대값을 저장해둔다.
최소 필요 피로도가 현재 피로도보다 작을 때 dfs를 실행한다.
DFS에서 빠져나올 때 소비한 피로도를 다시 더해주고 visited = true로 바꿔준다.
코드
/**
최소 필요 피로도
해당 던전 탐험 위해 가지고 있어야 하는 최소한의 피로도
소모 피로도
던전 탐험 후 소모되는 피로도
던전들을 최대한 많이 탐험하려고 함
parameter
유저의 현재 피로도 1 <= k <= 5000
2차원 배열 dungeons 2 x 1~8
최소 필요 피로도, 소모 피로도
각 던전별 "최소 필요 피로도"
각 던전별 "소모 피로도"
1 <= 최소 필요 피로도 >= 소모 피로도 <= 1000
return
유저가 탐험할 수 있는 최대 던전 수
DFS(던전 배열, 현재 피로도, 현재 거쳐온 던전 수)
최소 필요 피로도가 현재 피로도보다 작을 때 dfs 실행
DFS에서 빠져나올 때 소비한 피로도를 다시 더해주고 visited = true로 바꿔줌
**/
class Solution {
static boolean[] visited;
static int answer = -1;
public int solution(int k, int[][] dungeons) {
visited = new boolean[dungeons.length];
DFS(k, dungeons, 0);
return answer;
}
public void DFS(int k, int[][] dungeons, int cnt){
answer = Math.max(answer, cnt);
for(int i=0; i<dungeons.length; i++){
if(visited[i] == false && dungeons[i][0] <= k){
// 최소 필요 피로도가 현재 피로도보다 작을 때
visited[i] = true;
k -= dungeons[i][1];
DFS(k, dungeons, cnt+1);
visited[i] = false;
k += dungeons[i][1];
}
}
}
}