[프로그래머스][LEVEL2] 피로도

# 문제 원문

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

 

# 문제 풀이

 

네오플의 던전 앤 파이터가 떠오르는 문제. 완전탐색으로 접근해서 모든 경우의 수를 체크함으로 간단히 풀 수 있다. 제한 사항으로 입력 받는 던전 리스트가 8까지 유동적이라는 점 때문에 재귀함수를 활용해서 간단히 풀었다. FP 스타일로 풀어보려고 했지만 아직 미흡해서 그런가 간결하지 못하다. 입력 받은 dungenons의 모든 조합을 입력 받은 k에 연산하여서 최대 몇개의 던전을 클리어 가능한지 계산하는 문제이다.

 

# 솔루션 플로우

1. 입력 받은 dungeons를 순회한다.

2. 입력 받은 dungenons의 모든 경우의 수를 입력 받은 k와 비교해서 count 한다. 

4. 가장 많은 던전을 클리어한 경우의 count를 얻는다.

5. 얻어진 result를 반환한다.

1. 재귀 & 완전 탐색

function solution(k, dungeons) {
    return dungeons.reduce((result, current, idx) => {
        let count = 0;
        let state = k;
        if (current[0] <= state) {
            state -= current[1];
            count++;

            const next = Array.from(dungeons);
            next.splice(idx, 1);
            loop(next);
        }

        return result;

        function loop(dungeons) {
            dungeons.forEach((current, idx) => {
                if (current[0] <= state) {
                    state -= current[1];
                    count++;
                    if (dungeons.length > 0) {
                        const next = Array.from(dungeons);
                        next.splice(idx, 1);
                        loop(next);
                    }
                    result = count > result ? count : result;
                    state += current[1];
                    count--;
                }
            });
        }
    }, 0);
}