https://school.programmers.co.kr/learn/courses/30/lessons/87946
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
탐험 가능한 최대 던전 수를 찾는 문제이므로 깊이 우선 탐색을 사용했다.
전형적인 깊이 탐색 소스라서 코멘트할 내용이 없다...
class Solution {
int answer = 0;
public int solution(int k, int[][] dungeons) {
boolean[] check = new boolean[dungeons.length];
explorer(k, dungeons, check, 0);
return answer;
}
void explorer(int k, int[][] dungeons, boolean[] check, int cnt) {
for(int i=0; i<dungeons.length; i++){
if(!check[i] && dungeons[i][0] <= k){
check[i] = true;
explorer(k - dungeons[i][1], dungeons, check, cnt + 1);
check[i] = false;
}
}
answer = Math.max(answer, cnt);
}
}
