🔵 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/87946
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
🔵 문제 접근
문제에서 제시된 던전의 최대 개수는 8이므로 매우 적다.
따라서 던전을 입장하는 모든 순서를 탐색해 풀이할 수 있다.
백트래킹으로 풀이하였다.
🔵 전체 코드
#include <string>
#include <vector>
using namespace std;
// 최소 피로도 , 소모 피로도
// 최대한 많은 던전을 탐험하기
// 던전의 개수 최대 1 ~ 8 (매우 작음)
int ans;
bool visited[8];
void backtracking(int stamina, const vector<vector<int>>& dungeons, int count)
{
// 던전을 들어간 순간 카운팅
ans = max(ans, count);
// 던전을 방문하는 모든 조합을 탐색
for (int i = 0; i < dungeons.size(); i++)
{
int require = dungeons[i][0];
int use = dungeons[i][1];
if (require <= stamina && visited[i] == false)
{
visited[i] = true;
backtracking(stamina - use, dungeons, count + 1);
visited[i] = false;
}
}
}
int solution(int k, vector<vector<int>> dungeons)
{
vector<bool> visited(dungeons.size(), false);
backtracking(k, dungeons, 0);
return ans;
}
🔵 시간 복잡도
던전의 개수를 N이라 할 때, 최악의 경우 모든 경로를 탐색하므로 시간 복잡도는 O(N!)이다.
하지만 실제로는 for문 안의 if 조건(유망 함수)에 따라 걸러지므로 훨씬 적게 연산한다.
'PS' 카테고리의 다른 글
| [C++] Programmers Lv. 3 "외벽 점검" (0) | 2025.07.04 |
|---|---|
| [C++] Programmers Lv. 2 "양궁대회" (0) | 2025.07.03 |
| [C++] Programmers Lv. 2 "전력망을 둘로 나누기" (2) | 2025.06.25 |
| [C++] Programmers Lv. 3 "경주로 건설" (0) | 2025.06.24 |
| [C++] Programmers Lv. 2 "배달" (5) | 2025.06.18 |