[프로그래머스] 피로도 with JS

알고리즘 스프린트 9일차 - [프로그래머스] Lv 2. 멀쩡한 사각형

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

프로그래머스

소요시간

15분..

 

계획

던전의 개수가 너무 적어서 어떻게 풀어도 상관없을 것 같아서 DFS로 푸는 모습

 

풀이

• DFS
  
  • check 배열과 k값을 감소시키면서 탐색했다
  • 반복문으로 모든 던전 돌면서
  • 현재 피로도로 들어갈 수 있는지 탐색했던 곳은 아닌지 확인한다
  • 두 조건 다 만족할 경우 다음 깊이로 들어간다

결과

코드

var answer = 0;

function solution(k, dungeons) {
    let check = dungeons.map(d => false);
    dfs(k, dungeons, check.slice(), 0)
    return answer;
}

function dfs(k, dungeons, check, count){
    answer = answer < count ? count : answer;
    for(let i = 0; i < dungeons.length; i++){
        if(!check[i] && dungeons[i][0] <= k){
            check[i] = true;
            dfs(k-dungeons[i][1], dungeons, check.slice(), count+1);
            check[i] = false;
        }
    }
}

마치며

어느덧 알고리즘 스프린트를 달린지 9일차가 되었다. 오늘 문제는 조금 쉬웠다.. 점점 폼이 올라오고 있는 것 같다. 내일부터는 난이도를 좀 올려서 풀어볼까한다..!