프로그래머스 - 피로도 (위클리 챌린지 12주차)

1. 문제

문제 링크

설명

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

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

제한사항

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

입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

2. 풀이

잡담

위클리 챌린지가 마지막 주라는 사실을 아시나요?
정말 손살같이 지나간 12주였습니다.
그동안 '좋아요'좀 많이 받아서 기프티콘 좀 얻겠다고
매주 월요일마다 고분분투하던 일도 이제는 추억이 되겠네요 ㅎㅎ
근데 12주 동안 '좋아요' 단 한 개도 못 받은 거 실화?

풀이

마지막 주차의 문제는 꽤 단순했습니다.

1. 던전을 탐색하는 모든 경우의 수를 만들기
   • 백트래킹을 이용한 순열 만들기
   • C++의 next_permutation함수 활용
2. 각 경우마다 탐험 가능한 던전 개수 계산해서 최댓값 갱신

매우 간단한 백트래킹 문제라 볼 수 있습니다.

처음 제출한 코드

function solution(k, dungeons) {
    const N = dungeons.length;
    const used = Array(N).fill(0);
    const permutation = Array(N).fill(0);

    return (function f(depth) {
        if (depth == N) {
            // 탐험할 수 있는 던전 개수 계산
            let i = 0;
            let K = k;

            for (; i < N; i++) {
                if (K < dungeons[permutation[i]][0]) break;

                K -= dungeons[permutation[i]][1];
            }

            return i;
        }

        let ret = 0;
      
	// 모든 순열 만들기
        for (let i = 0; i < N; i++) {
            if (used[i]) continue;

            permutation[depth] = i;
            used[i] = 1;
            ret = Math.max(ret, f(depth + 1));
            used[i] = 0;
        }

        return ret;
    })(0);
}

물론 잘 통과됐지만
기저 사례에서 몇 개의 던전을 탐험할 수 있는지 계산하는 게 아니라,
탐험해 나가면서 계산하는 방식이 더 빠릅니다.
왜냐하면 이미 피로도가 적어서 뒤에 있는 던전을 탐험할 수 없는데,
전자의 방식은 그 뒤에 있는 던전을 탐험하는 경우의 수도 만들고 있기 때문에 비효율적입니다.

자세한 내용은 코드를 보면 이해할 수 있습니다.

최종 코드

function solution(k, dungeons) {
    const N = dungeons.length;
    const used = Array(N).fill(0);

    return (function f(depth, rest) {
        // 피로도를 다 사용했거나, 던전을 다 돌았을 때
        if (rest <= 0 || depth == N) return depth;

        let ret = depth;

        for (let i = 0; i < N; i++) {
            if (used[i]) continue;

            // 현재 남은 피로도 < 던전이 요구하는 피로도
            if (rest < dungeons[i][0]) continue;

            used[i] = 1;
            ret = Math.max(ret, f(depth + 1, rest - dungeons[i][1]));
            used[i] = 0;
        }

        return ret;
    })(0, k);
}

순열을 만들되, 만들면서 탐험해 나가는 겁니다.
테스트 결과 눈에 보이는 성능 차이는 없지만 던전의 개수가 많을수록 차이는 극명해질 겁니다.

더 개선을 한다면 정답은 dougeons.length보다 클 수가 없습니다.
그렇기 때문에 어떤 경우에서 dougeons.length만큼 탐험이 가능하다면,
나머지 경우는 볼 필요도 없이 dougeons.length를 리턴해도 됩니다.