문제
https://school.programmers.co.kr/learn/courses/30/lessons/87946
입력
- 유저의 현재 피로도 k
- 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons
출력
- 유저가 탐험할수 있는 최대 던전 수
풀이
제한조건
- k는 1 이상 5,000 이하인 자연수입니다.
- dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
- dungeons의 가로(열) 길이는 2 입니다.
- "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
- "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
- 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
접근방법
완전 탐색, 백트래킹
완전 탐색, 백트래킹 유형으로 문제를 풀 수 있다.
쉬운 문제일수록 가지 치기의 필요가 없는 완전 탐색으로 풀리는 경우가 많으며,
조금 더 까다롭게 출제된 문제는 가지 치기(백트래킹)을 요구한다.
시작 전, 문제를 보면 방문 순서가 관련이 있다는 것을 알 수 있다.
(예시만 읽어봐도 방문 순서에 따라, 탐험 가능한 던전의 수가 달라짐을 알 수 있다.)
따라서 조합이 아닌 순열로 접근할 필요가 있음을 유의하자.
우선 조금 더 단순한 완전 탐색부터 시작해보자.
완전 탐색
말 그대로 완전 탐색이다.
일반적인 완전 탐색의 경우 아래 그림과 같이 뻗어나가며 탐색하면 된다
하지만 이 문제의 경우, 방문 순서에 따라 관련이 있으므로 우선 나올 수 있는 순열을 먼저 구해야 한다
최대 8개밖에 주어지지 않으므로 나올 수 있는 경우를 우선 모두 뽑아보자.
만약 던전이 3개인 경우
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1순서가 정해졌다면, 문제의 조건에 맞게 최소 피로도와 소모 피로도를 고려해가며 값을 계산하면 된다.
백트래킹, 가지치기
위의 케이스를 한 번 다시 살펴보자.
최소 피로도와 소모 피로도를 고려해서 탐색을 한다.
위의 가지에서 사실 끝까지 탐색해보지 않아도 결과를 아는 케이스가 존재한다.
그런 케이스를 끝가지 탐색하지 않고 중간에 생략하기만 해도 불필요한 연산의 수가 크게 줄어든다.
재귀적으로 탐색을 호출하기 직전에 미리 계산을 해보자.
코드
백트래킹
class Solution {
int result, maxDepth;
int[][] arr;
boolean[] isSelected;
public int solution(int k, int[][] dungeons) {
arr = dungeons;
maxDepth = dungeons.length;
isSelected = new boolean[maxDepth];
permutaion(k, 0, 0);
return result;
}
public void permutaion(int remain, int depth, int count) {
result = result > count ? result : count;
if (maxDepth == depth)
return;
for (int i = 0; i < maxDepth; ++i) {
if (!isSelected[i] && remain >= arr[depth][0]) {
isSelected[i] = true;
permutaion(remain - arr[depth][1], depth + 1, count + 1);
isSelected[i] = false;
}
}
}
}완전탐색
class Solution {
int result, maxDepth;
int[][] arr;
boolean[] isSelected;
int[] permArr;
public int solution(int k, int[][] dungeons) {
arr = dungeons;
maxDepth = dungeons.length;
isSelected = new boolean[maxDepth];
permArr = new int[maxDepth];
permutaion(k, 0);
return result;
}
public void permutaion(int remain, int depth) {
if (maxDepth == depth) {
int count = 0;
for (int index : permArr) {
if (remain >= arr[index][0]) {
remain -= arr[index][1];
count++;
continue;
}
break;
}
result = result > count ? result : count;
return;
}
for (int i = 0; i < maxDepth; ++i) {
if (!isSelected[i]) {
isSelected[i] = true;
permArr[depth] = i;
permutaion(remain, depth + 1);
isSelected[i] = false;
}
}
}
}