프로그래머스 2단계 : 피로도 (Java 자바)

문제 설명

 

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)를 이용하여, 유저가 탐험할 수 있는 최대 던전 수를 계산하는 문제를 해결하는 문제입니다. 

 

1. solution 메서드는 던전 탐험의 시작점입니다. k는 현재 남은 피로도를 나타내고, dungeons는 던전 정보를 담은 2차원 배열입니다. 이 메서드는 explore 메서드를 호출하고, 최대 탐험 가능한 던전 수인 max를 반환합니다.

2. explore 메서드는 재귀적으로 던전을 탐험합니다. 현재 남은 피로도(k)로 방문하지 않은 던전을 순회하며 각 던전을 탐험할 수 있는지 검사합니다. 만약 탐험 가능하다면 해당 던전을 방문하고, 재귀적으로 다음 던전으로 진행합니다. 재귀 호출 후에는 방문한 던전을 방문 해제합니다.
3. max 변수에는 최대 탐험 가능한 던전 수가 저장됩니다.
모든 가능한 던전 탐험 경로를 탐색하며 최대 탐험 가능한 던전 수를 찾습니다.

 

class Solution {
    public int solution(int k, int[][] dungeons) {
        int[] visited = new int[dungeons.length]; // 던전 방문 여부를 나타내는 배열
        explore(dungeons, visited, k, 0); // 던전 탐험을 시작하는 재귀 함수 호출
        
        return max; // 최대 탐험 가능한 던전 수 반환
    }
    
    private int max = 0; // 최대 탐험 가능한 던전 수를 저장하는 변수
    
    private void explore(int[][] dungeons, int[] visited, int k, int count) {
        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i] == 0 && k >= dungeons[i][0]) {
                visited[i] = 1; // 던전을 방문 처리
                explore(dungeons, visited, k - dungeons[i][1], count + 1); // 다음 던전으로 재귀 호출
                visited[i] = 0; // 던전 방문 해제 (다음 경우의 탐험을 위해)
            }
        }
        
        if (max < count) {
            max = count; // 현재까지의 최대 탐험 가능한 던전 수 업데이트
        }
    }
}