피로도

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

프로그래머스

문제 설명

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

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

제한사항

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

입출력 예 설명

현재 피로도는 80입니다.

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

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

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

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

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

 

풀이

class Solution {
    static int count = 0;
    static boolean[] explored;
    
    public int solution(int k, int[][] dungeons) {
        explored = new boolean[dungeons.length];
        recursion(0,k,dungeons);
        return count;
    }
    
    public void recursion(int cleared, int fatigue, int[][]dungeons){
        for(int i=0;i<dungeons.length;i++){
            if(explored[i] || fatigue < dungeons[i][0]){
                continue;
            }
            explored[i] = true;
            recursion(cleared+1,fatigue - dungeons[i][1], dungeons);
            explored[i] = false;
        }
        count = Math.max(count, cleared);
    }
}

재귀와 백트래킹을 이해하면 쉽게 풀 수 있는 문제였다. 이를 위해 static으로 탐험 성공의 경우의 수들 중 최대로 계속 업데이트해줄 count, 이를 위해 던전별 탐험 유무를 알기위해 explored 배열을 생성해 주었다. 먼저 recursion 함수를 보면 매개변수로 탐험에 성공한 던전의 개수를 저장하는 cleared, 피로도를 뜻하는 fatigue, 던전을 받도록 하였다. 이를 사용하여 for문에서 explored[i]를 확인하여 탐험을 한 던전이거나 현재 피로도가 던전별 최소 필요 필요도보다 적은지를 확인하여 || 로 둘중 하나라도 해당이 된다면 건너 뛰고 다른 경우의 수를 계속 찾도록 하였다. 밑에서는 if문을 통과하였으므로 피로도상 탐험이 가능한 던전이므로 explored를 탐험 할 것이므로 true로 바꾸어주고 재귀함수를 다시 실행하는데 이때 cleared 는 +1을 해주어 탐험성공횟수를 증가시켜주고 피로도에서는 최소필요도를 빼준 값을 매개변수로 주는 방식으로 값들은 업데이트 해주면서 재귀문을 모든 값에 대해서 수행되도록 구현 할 수 있었다.. explored[i] = false 부분은 백트래킹을 위한 부분이다. 그 뒤 Math.max 함수를 사용해서 count를 최대 값으로 업데이트 해주었고. solution에서 재귀문을 한번 호출후 count값을 리턴해주면 구현에 성공할 수 있었다.