프로그래머스 | Level 2 | 피로도
Programmers | Level 2 | 피로도
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Brute Force
Description
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
Constraints
k는 1 이상 5,000 이하인 자연수입니다.dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.dungeons의 가로(열) 길이는 2입니다.dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"]입니다.- "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
- "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
- 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
Examples
| k | dungeons | result |
|---|---|---|
| 80 | [[80, 20], [50, 40], [30, 10]] | 3 |
Solutions
- ⏳ TC: O(n!)
- 💾 SC: O(n)
import java.util.*;
class Solution {
private int maxCount = 0; // 최대 탐험 던전 수 저장
public int solution(int k, int[][] dungeons) {
boolean[] explored = new boolean[dungeons.length]; // 던전 탐험 상태 추적
explore(k, dungeons, explored, 0); // 던전 탐험 시작
return maxCount; // 최대 탐험 던전 수 반환
}
private void explore(int k, int[][] dungeons, boolean[] explored, int count) {
for (int i = 0; i < dungeons.length; i++) {
int hpRequired = dungeons[i][0]; // 최소 필요 피로도
int hpLost = dungeons[i][1]; // 소모 피로도
if (!explored[i] && k >= hpRequired) { // 탐험 가능한 던전
explored[i] = true; // 던전 탐험 상태 설정
explore(k - hpLost, dungeons, explored, count + 1); // 재귀 호출
explored[i] = false; // 탐험 상태 초기화: 다음 던전 탐험을 위해 상태를 초기화
}
}
maxCount = Math.max(maxCount, count); // 최대 탐험 던전 수 갱신
}
}
Approaches
이 문제는 완전 탐색(Brute Force) 접근 방식을 사용하여 주어진 던전들을 탐험할 수 있는 모든 순서를 시도해보고, 그중 최대 탐험할 수 있는 던전 수를 찾아내는 문제입니다. 완전 탐색은 가능한 모든 경우의 수를 시도하여 최적의 해답을 찾는 방법입니다. 이 문제에서는 각 던전을 탐험하는 순서를 결정하기 위해 가능한 모든 순열을 생성하고, 각 순열에 대해 던전을 탐험하면서 최대 탐험 가능한 던전 수를 계산합니다. 순열을 사용하는 이유는 던전의 탐험 순서가 결과에 영향을 미치기 때문에, 가능한 모든 순서를 시도해 봄으로써 최적의 해답을 찾기 위함입니다.
순열(Permutation)이란 주어진 요소들의 모든 가능한 순서를 의미합니다. 예를 들어, [A, B, C]라는 세 개의 요소가 있을 때, 이 요소들의 모든 순열은 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A] 총 6가지가 됩니다. 이 문제에서는 던전의 탐험 순서를 순열로 생성하여 모든 가능성을 고려하는 것입니다.
이를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:
- 모든 순서에 대한 탐색 시도:
- 주어진 던전들의 모든 순서를 생성합니다. 이는 각 던전의 탐험 순서를 결정하기 위해 모든 가능한 경우의 수를 시도하는 것입니다. 예를 들어, 주어진 던전이 3개라면 가능한 순서는 3! = 6개입니다. 이를 통해 모든 가능한 던전 탐험 순서를 고려할 수 있습니다.
- 순열 생성:
- 순열(Permutation)은 특정 순서에 따라 배열된 요소들의 집합입니다. 이 문제에서는 던전들을 탐험할 수 있는 모든 순서를 의미합니다.
- 주어진 던전들의 모든 순열을 재귀 호출을 통해 생성합니다. 이는 각 던전의 탐험 순서를 바꾸어가며 가능한 모든 경우를 시도하기 위함입니다.
- 탐험 시뮬레이션:
- 각 순열에 대해 던전을 탐험합니다.
- 현재 피로도를 기준으로 각 던전을 탐험할 수 있는지 확인하고, 탐험이 가능하면 "소모 피로도"를 차감합니다.
- 탐험할 수 없는 경우 해당 순서에서는 더 이상 진행하지 않습니다.
- 최대 탐험 가능한 던전 수 추적:
- 각 순서에 대해 탐험한 던전 수를 계산하고, 그중 최대 값을 추적합니다.
- 최종적으로 최대 탐험 가능한 던전 수를 반환합니다.
이 알고리즘은 주어진 던전의 모든 순서를 시도해보기 때문에 시간 복잡도는 O(n!)입니다. 하지만 던전의 개수가 최대 8개로 제한되어 있기 때문에 실제 실행 시간은 충분히 빠릅니다.
- Algorithm
- Greedy