2026.04.08
문제 설명
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- k는 1 이상 5,000 이하인 자연수입니다.
- dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
- dungeons의 가로(열) 길이는 2 입니다.
- dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
- "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
- "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
- 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
입출력 예
문제 풀이
1차 실행 오류
코드에서 사용된 던전 입장 피로도와 소모 피로도의 비율을 구해
내림차순으로 정렬하여 해결하는 알고리즘 자체가 잘못되었음
import java.util.Map;
import java.util.TreeMap;
import java.util.Collections;
class Solution {
public int solution(int k, int[][] dungeons) {
int answer = 0;
// 해시맵 내림차순으로 정렬
Map<Double, Integer> sorted = new TreeMap<>(Collections.reverseOrder());
// 필요 필요도와 소모 필요도 비율 계산하여 해시맵에 저장
for (int i = 0; i < dungeons.length; i++) {
double ratio = dungeons[i][0] / dungeons[i][1];
sorted.put(ratio, i);
}
for (int i : sorted.values()) {
if (k < dungeons[i][0]) {
break;
}
else {
k -= dungeons[i][1];
answer++;
}
}
return answer;
}
}2차 실행 오류
나눠서 비율을 계산하기보다, 필요 피로도 - 소모 피로도로 정리하였음
실패는 현저히 줄었지만, 여전히 오류가 나는 경우의 수가 있음
Hash의 특성상 같은 key값을 가지면 덮어씌워지는 문제가 발생함
import java.util.Map;
import java.util.TreeMap;
import java.util.Collections;
class Solution {
public int solution(int k, int[][] dungeons) {
int answer = 0;
// 해시맵 내림차순으로 정렬
Map<Integer, Integer> sorted = new TreeMap<>(Collections.reverseOrder());
// 필요 필요도와 소모 필요도 비율 계산하여 해시맵에 저장
for (int i = 0; i < dungeons.length; i++) {
int ratio = dungeons[i][0] - dungeons[i][1];
sorted.put(ratio, i);
}
for (int i : sorted.values()) {
if (k < dungeons[i][0]) {
continue;
}
else {
k -= dungeons[i][1];
answer++;
}
}
return answer;
}
}3차 실행 오류
알고리즘 자체가 잘못되었음.
필요 피로도와 소모 피로도로 푸는 것이 아닌, DFS로 풀어야함
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public int solution(int k, int[][] dungeons) {
int answer = 0;
Map<Integer, Integer> map = new HashMap<>();
// 필요 필요도와 소모 필요도 비율 계산하여 해시맵에 저장
for (int i = 0; i < dungeons.length; i++) {
int ratio = dungeons[i][0] - dungeons[i][1];
map.put(i, ratio);
}
List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(map.entrySet());
Collections.sort(entries, (a, b) -> b.getValue() - a.getValue());
for (Map.Entry<Integer, Integer> entry : entries) {
int i = entry.getKey();
if (k < dungeons[i][0]) {
continue;
}
else {
k -= dungeons[i][1];
answer++;
}
}
return answer;
}
}지금까지 소요 시간: 58분
AI 코드
완전탐색(Brute-Force)
모든 경우의 수를 전부 시도해보는 방법
완전탐색 알고리즘
- 1) 너비 우선 탐색(Breadth-First Search, BFS)
시작점에서 가까운 곳 부터 탐색, 최단 경로 문제에 적합
1
/ \
2 3
/ \ / \
4 5 6 7
탐색 순서: 1 → 2 → 3 → 4 → 5 → 6 → 7- 2) 깊이 우선 탐색(Depth-First Search, DFS)
한 방향으로 끝까지 탐색 후 되돌아옴, 모든 경우 탐색에 적합
1
/ \
2 3
/ \ / \
4 5 6 7
탐색 순서: 1 → 2 → 4 → 5 → 3 → 6 → 7-
3) 백트래킹
DFS + 가지치기, 조건 있는 검색에 적합
조건에 맞지 않으면 더 이상 탐색하지 않음
불필요한 탐색을 줄여서 DFS보다 빠름 -
4) DFS + 백트래킹
순열/조합 문제에 적합
완전탐색이 필요한 경우
- 1) 입력 크기가 매우 작을 때
입력 크기가 작으면 완전탐색을 의도한 문제일 가능성이 있음
2) 최적의 순서/조합을 보장하는 기준이 없을 때
- greedy → 특정 기준으로 정렬하면 항상 최적임이 증명되어야 함
- DFS → 증명이 되지 않는 경우
3) 모든 경우의 수를 따져야 할 때
- 순열 → 순서가 중요할 때
- 조합 → 순서가 중요하지 않을 때
- 부분집합 → 포함/미포함 선택할 때
문제를 보고 판단하는 법
- 입력 크기 작음(n ≤ 10)
- "최대한 많이", "최댓값"
- greedy 기준을 찾기 어려울 때
입력 크기가 작을 때 완전탐색을 의심해볼 것
재귀 진행과정 정리
class Solution {
boolean[] visited;
int answer = 0;
public int solution(int k, int[][] dungeons) {
visited = new boolean[dungeons.length];
dfs(k, dungeons, 0);
return answer;
}
public void dfs(int k, int[][] dungeons, int count) {
answer = Math.max(answer, count);
for (int i = 0; i < dungeons.length; i++) {
if (!visited[i] && k >= dungeons[i][0]) { // 방문가능한 조건
visited[i] = true;
dfs(k - dungeons[i][1], dungeons, count + 1);
visited[i] = false;
}
}
}
}