[Java] 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제 설명

일정 피로도를 사용해 던전 탐험 가능.
각 던전마다 탐험을 시작하기 위해 필요한 최소 필요 피로도 와 던전 탐험을 마쳤을때 소모되는 소모 피로도 존재.

최소 필요 피로도: 탐험을 위해 가지고 있어야 하는 최소한의 피로도.
소모 피로도: 던전 탐험 후 소모되는 피로도.

예를들어, 최소 필요 피로도: 80, 소모 피로도: 20인 탐험하기 위해, 현재 피로도는 80 이상이어야 하며, 던전 탐험 후 피로도 20 소모됨.

현재 피로도 k, 각 던전별 최소 피로도, 소모 피로도가 담긴 2차원 배열 dungeons가 주어질때, 유저가 탐험할 수 있는 최대 던전 수 return.

입출력 예

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

풀이

[1차 생각]

1. 정렬

• 현재 피로도가 탐험에 필요한 최소 피로도가 이상일때,

• 던전에서 소모되는 피로도는 적을수록 좋다.
  가령, 입출력 예에서 [50,40]보다 [30,10]을 먼저 탐험했을때 최대로 탐험할 수 있듯이.

-> 해당 기준을 바탕으로 dungeons을 정렬한다.

즉, 최소 피로도는 내림차순으로, 피로도는 오름차순으로 정렬하기.

2. 던전 탐험
   완전 탐색하면서, 탐험 최댓값 반환.

.. 근데, dungeons의 배열 순서를 어떻게 바꾸지?

-> 가능한 dungeons의 순열을 생성하는 재귀함수 만들기.

[2차 생각]

재귀함수를 만들기 위해, 필요한 인자, 변수를 생각해보자.

• 방문 체크 배열: visited
• 탐험 횟수: cnt

private void recur(int k, int [][]dungeons, boolean[] visited, int cnt)

정답코드

import java.util.*;

class Solution {
    private int maxExplored;
    
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        
        boolean[] visited = new boolean[dungeons.length]; // 방문 배열
        recur(k, dungeons, visited, 0);
        
        return maxExplored;
    }
    
    private void recur(int k, int[][] dungeons, boolean[] visited, int cnt ){
        
        // 탐험
        for(int i=0; i<dungeons.length; i++){
            // 방문 x && 현재 피로도 >= 최소 피로도
            if(!visited[i] && k>= dungeons[i][0]){
                // 방문 체크
                visited[i]=true;
                // 현재 피로도, 방문체크, 탐험횟수+1 갱신한 재귀 함수 실행
                recur(k-dungeons[i][1], dungeons, visited,cnt+1 );
                // 실행 후 방문체크 되돌려 다른 순서 탐험 가능하도록.
                visited[i]=false;
            }
            // 최댓값 구하기
            maxExplored = Math.max(cnt, maxExplored);
        }
    }
}

재귀는 어렵다,,