[프로그래머스_위클리 챌린지]피로도

문제

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

kdungeonsresult

80

[[80,20],[50,40],[30,10]]

3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

 

문제풀이

https://choi95.tistory.com/137?category=881084

[냅색 알고리즘]동전교환

일전에 풀었던 동전교환 문제와 같이 사용자의 남아 있는 피로도를 기준으로 각 소비 피로도에 따라 돌 수 있는 최대 던전의 횟수를 냅색 알고리즘을 통해 풀이하였다.

 

코드

function solution(k, dungeons) {
    var answer = -1;
    let dy = Array.from({length: k + 1}, () => 0);

    for(let i = 0; i < dungeons.length; i++) {
        let need = dungeons[i][0];
        let spend = dungeons[i][1];
        for(let j = k; j >= spend; j--) {
            dy[j] = Math.max(dy[j], dy[j - spend] + 1)
        }
    }
    
    answer = dy[k];
    
    return answer;
}

 

오답

예시 케이스는 모두 통과하였지만 몇 개의 테스트 케이스에서 오답 처리되었다.

 

원인을 찾아보니 DP를 통해 풀게 되면 모든 경우 수에 대해서 처리하지 못함을 확인할 수 있었다.

 

해당 문제는 던전을 방문하는 순서가 별도로 지정되어 있지 않다.

그래서 만약에 입장에 필요한 피로가 큰 순서대로 간다면 3번째 던전을 못 돌기 때문에 안되며 반대로 작은 순서대로 가게 된다면 입장에 필요한 피도도가 큰 것이 나중에 나오기 때문에 모든 경우의 수를 파악하지 못하는 문제가 있다.

 

이에 던전의 진행 횟수를 depth로 지정하고 던전의 방문 여부와 던전을 통과한 시점에 남은 피로도를 별도로 계산해주는 깊이 탐색(DFS)을 통해 문제를 풀이해야 됨을 확인하였다.

 

코드

function solution(k, dungeons) {
        let max = Number.MIN_SAFE_INTEGER;

        function DFS(f, pass, nonPass) {
          if (dungeons.length === pass.length + nonPass.length) {
            max = max > pass.length ? max : pass.length;
          } else {
            for (let i = 0; i < dungeons.length; i++) {
              if (!pass.includes(i) && !nonPass.includes(i)) { // 방문 여부를 확인
                if (f >= dungeons[i][0]) { // 남아 있는 피로도가 더 많을 경우
                  pass.push(i);
                  DFS(f - dungeons[i][1], pass, nonPass);
                  pass.pop();
                } else { // 남아 있는 피로도가 모자란 경우
                  nonPass.push(i);
                  DFS(f, pass, nonPass);
                  nonPass.pop();
                }
              }
            }
          }
        }
        DFS(k, [], []);
        return max;
      }