피로도

문제 설명

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

입출력 예 설명

현재 피로도는 80입니다.

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

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

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

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

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

모든 가능한 던전 탐험 순서를 고려하고, 최대한 많은 던전을 탐험하는 순서를 찾는 것이다. 이러한 문제는 일반적으로 "백트래킹" 알고리즘을 사용하여 해결할 수 있다.

package LV2;

public class H87946 {
    // 최대 탐험 가능한 던전 수를 저장할 변수
    int answer = 0;

    public int solution(int k, int[][] dungeons) {
        // 각 던전을 방문했는지 여부를 체크하는 배열
        boolean[] visited = new boolean[dungeons.length];

        // 깊이 우선 탐색(DFS)를 시작
        dfs(k, dungeons, visited, 0);

        // 최대 탐험 가능한 던전 수를 반환
        return answer;
    }

    // 깊이 우선 탐색(DFS)을 수행하는 메소드
    private void dfs(int fatigue, int[][] dungeons, boolean[] visited, int count) {
        // 현재까지 탐험한 던전 수(count)와 answer 중 큰 값을 answer로 저장
        answer = Math.max(answer, count);

        // 모든 던전에 대해서
        for (int i = 0; i < dungeons.length; i++) {
            // 아직 방문하지 않은 던전이고, 현재 피로도가 던전의 최소 필요 피로도 이상인 경우
            if (!visited[i] && fatigue >= dungeons[i][0]) {
                // 해당 던전을 방문했음을 표시
                visited[i] = true;

                // 던전의 소모 피로도를 현재 피로도에서 빼고, 다음 던전을 탐험하기 위해 재귀 호출합
                dfs(fatigue - dungeons[i][1], dungeons, visited, count + 1);

                // 백트래킹: 던전 탐험을 마치고 해당 던전의 방문 상태를 원래대로 되돌린다.
                visited[i] = false;
            }
        }
    }
}

1. **answer**를 0으로 설정하여 최대 던전 탐험 횟수를 기록한다.
2. solution 함수는 입력된 피로도 **k**와 던전 정보를 받아서 dfs (깊이 우선 탐색)를 호출한다. 던전에 방문한 표시를 위한 visited 배열과 현재까지 탐험한 던전의 개수를 0으로 설정한다.
3. dfs 함수는 현재 남은 피로도, 던전 정보, 방문한 던전의 상태, 그리고 현재까지 탐험한 던전의 수를 입력으로 받는다. 각각의 재귀 호출에서는 **answer**를 현재까지 탐험한 던전의 수와 비교하여 더 큰 값을 **answer**에 저장한다.
4. **dfs**는 모든 던전에 대해 현재 던전을 탐험할 수 있는지 (즉, 현재 피로도가 최소 필요 피로도 이상인지, 그리고 해당 던전을 아직 방문하지 않았는지)를 확인한다. 만약 가능하다면, 해당 던전을 방문하고 남은 피로도를 업데이트한 후, 다음 던전을 탐험하기 위해 **dfs**를 재귀 호출한다. 이후 백트래킹을 위해 해당 던전의 방문 상태를 원래대로 되돌린다.
5. 마지막으로 solution 함수는 최대 던전 탐험 횟수를 반환한다.