[프로그래머스] 피로도 (완전탐색, JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=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 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다. 

입출력 예

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입니다.

---

※ JAVA 코드

 

class Solution {
    static int result = 0;
    static int energy = 0;
    
    public int solution(int k, int[][] dungeons) {
        energy = k;
        int len = dungeons.length;
        int out [][] = new int[len][2];
        boolean v [] = new boolean[len];
        permutation(dungeons, out, v, 0, len, len);
        
        int answer = result;
        return answer;
    }
    
    static void permutation(int dungeons[][], int output [][], boolean visited [], int depth, int n, int r) {
        if (depth == r) {
            int hp = energy;
            int cnt = 0;
            for(int i = 0; i < r; i++) {
                if(output[i][0] <= hp) {
                    cnt++;
                    hp -= output[i][1];
                } else {
                    break;
                }
            }
            
            if(result < cnt) {
                result = cnt;
            }
        }

        for (int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                output[depth][0] = dungeons[i][0];
                output[depth][1] = dungeons[i][1];
                permutation(dungeons, output, visited, depth + 1, n, r); // depth 증가
                visited[i] = false;
            }
        }
    }
}

---

※ 문제풀이

오랜만에 푸는 알고리즘문제.. 보자마자 순열이 떠올랐다면 맞다

로직은 다음과 같다

1. 던전 순서 정함

2. 현재 HP과 던전 최소 입장가능 HP 비교

3. 입장가능시 HP 소모후 카운트 증가

4. 다음 탐험 순서 획득

 

위를 반복한다.

순열을 통해 던전을 탐험하는 순서를  정하는데 이때 중복되는 던전은 없이 모든 던전을 탐험하려고 한다.

순열을 사용할 수 있었던 이유는 던전의 수가 8개로 제한되어 있기 때문이다.

nPr 최대 8개의 던전중 8개의 순서를 구하므로 n! / 1! = n! 즉 8!만큼의 반복이 일어난다. 계산해보니 대략 40320번이므로 충분히 시간안에 끝낼 수 있다.

만약, 던전의 수가 12개라면 5억번이상의 반복이 일어나니 꼭 시간복잡도를 대략적으로라도 계산후 로직을 실행해보아야한다.. 문제에서는 대놓고 순열을 쓰라고 8개의 던전만을 준듯 하다.

그 이후의 로직은 완전탐색 각 순열마다 카운트를 실행하여 가장 큰 카운트를 리턴해준다.

 

감사합니다.