XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
k | dungeons | result |
---|---|---|
80 | [[80,20],[50,40],[30,10]] | 3 |
https://school.programmers.co.kr/learn/courses/30/lessons/87946
function solution(k, dungeons) {
var answer = 0;
// 방문 체크용 배열
const visited = Array(dungeons.length).fill(false);
// count: 방문한 던전 수
// k: 현재 피로도
function dfs(count, k) {
for (let i = 0; i < dungeons.length; i++) {
// 현재 피로도가 소모 피로도 이상 && 방문하지 않은 던전일 경우
if (k >= dungeons[i][0] && !visited[i]) {
// 방문 체크
visited[i] = 1;
// count는 1 증가
// 갱신된 현재 피로도 = 이전 피로도 - 소모 피로도
dfs(count + 1, k - dungeons[i][1]);
// 백트래킹을 위해 방문 여부 초기화
visited[i] = 0;
}
}
// answer에 가장 깊이 들어간 진행단계 대입
answer = Math.max(count, answer);
}
// count = 0, k = k를 매개변수로 한 dfs 실행
dfs(0, k);
return answer;
}
방문 체크용 배열 생성(dungeons의 길이만큼 false로 채워져있는)
dfs
함수 구현
방문 체크
방문 여부 초기화
가장 깊게
들어간 진행단계 구하여 answer에 대입dfs
함수 호출
유저가 탐험할수 있는 최대 던전 수answer
return
dfs 활용하여 풀이!!