[프로그래머스] 피로도

처리조건

https://programmers.co.kr/learn/courses/30/lessons/87946

풀이

처음에는 가장 높은 피로도를 사용하는 던전순으로 sort하여 돌 수 있는 던전수를 계산하려고 했으나 던전마다 필요한 피로도가 있으므로 높은 피로도부터 던전을 도는것이 가장 많은 던전을 돌 수 있다고는 보장할 수 없다.

 

그래서 모든 던전을 도는 경우의 수를 구하고 가장 많은 깊이만큼 들어간 count를 반환해야할 것이다.

결국 순열과 조합을 써야한다. 순열과 조합에서는 현재 조합 할 요소가 사용중인지 아닌지를 체크하는 배열을 따로 만들어야하며 시작할 깊이가 있어야한다. 나는 던전의 수만큼 check 배열을 만들어서 false로 채웠고 dfs함수를 만들어서 깊이0부터 시작해서 던전의 수만큼 for문을 돌리기 시작할 것이다. 맨처음 던전을 들어가면 해당 인덱스의 check배열 인덱스를 true로 바꿔주며 깊이를 1개 더올리며 현재 피로도인 k에서 현재 던전의 소모피로도를 빼준 k를 다시 dfs에 넣어준다. 그럼 어떻게 될까

 

다시 dfs 함수가 돌면서 모든 던전의 수만큼 for문을 돌릴 것이다. 여기서 모두가 다시 조합되면 안되지않는가? 맞다. 그래서 check 함수에서 우리는 이미 첫번째 던전을 돌았다고 true로 만들어놨다. 그럼 false인 던전만 다시 조합을 하게 될것이며 남은 던전 중 한 순서대로 한 던전을 골라 해당 던전도 check에서 true로 다시 dfs로 들어가 반복을 하게 되며 남은 던전까지 조건에 맞게 다돌고나면 자신을 false로 바꿔주면서 나가게된다. 이 과정을 거쳐 모든 던전의 경우의 수를 만들어가면서 돌게되며 answer배열에 들어간 최대 던전 깊이만큼을 다 담아주게 되며 0부터 3까지 수가 담기게 된다.

최대 던전수는 결국 count로 최대로 얼마나 깊이있게 들어가 조합했냐는 것이다.

 

마지막에 최대 값을 Math.max로 반환해주면 된다. 순열과 조합을 이해하는 것이 중요하다.

function solution(k, dungeons) {
 
let answer =[]
let check = new Array(dungeons.length).fill(false)


function dfs(count,k){
 answer.push(count);
 for(let i=0; i<dungeons.length;i++){
   if(dungeons[i][0]<=k&&check[i]===false){
     check[i]=true;
     dfs(count+1,k-dungeons[i][1])
     check[i]=false
   }
 }
}
dfs(0,k)
return Math.max(...answer)
}