문제 설명
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입니다.
나의 풀이
문제의 분류도 완전탐색이므로 완전탐색 알고리즘을 이요하여 접근하면 되겠다.
내가 지금까지 풀어왔던 완전탐색류의 문제에서는 DFS만으로 풀어왔는데, 이번 문제는 백트래킹 형식으로 문제를 풀어야 했다. 탐색한 던전의 방문 여부를 체크해줘야했기 때문이다. (Visited)
문제의 입출력 예 설명에서 설명했듯이 피로도를 다 사용했지만 탐색해야할 던전이 남았을 경우 다시 뒤로 돌아가서 다른 던전부터 탐색해야 한다. 이를 위해 Visited[] 가 필요한 것이다.
class Solution {
int answer = -1;
boolean[] visited;
public int solution(int k, int[][] dungeons) {
visited = new boolean[dungeons.length];
dfs(dungeons, k, 0);
return answer;
}
public void dfs(int[][] dungeons, int k, int cnt) {
for (int i = 0; i < dungeons.length; i++) {
if (!visited[i] && dungeons[i][0] <= k) {
visited[i] = true;
dfs(dungeons, k - dungeons[i][1], cnt + 1);
visited[i] = false;
}
}
answer = Math.max(cnt, answer);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] arr = {{80, 20}, {50, 40}, {30, 10}};
solution.solution(80, arr);
}
}첫 번째 if문에서 방문하지 않았고, 요구 피로도보다 현재 피로도가 많은 경우에만 탐색을 시작한다. 방문 이후에 방문 처리를 해주고, 다시 재귀함수로 자기 자신을 호출하는데, 이때 현재 피로도에서 탐색한 던전의 소모 피로도를 차감시키고 cnt를 증가시켜준다.
이렇게 재귀를 이용해서 구현하게 되면 피로도와 cnt의 증감 처리를 해주지 않아도 조건문 혹은 종료 시점에서 조건을 만족하지 못하면 재귀 함수를 탈출함과 동시에 피로도와 cnt도 재귀 함수 이전으로 돌아오기 때문에 보다 간편하게 코드를 작성할 수 있다.
