https://school.programmers.co.kr/learn/courses/30/lessons/87946
문제 해결 과정
착안
최소 필요 피로도 또는 소모 피로도로 정렬을 통해 해결할 수 있는 방법이 마땅히 떠오르지 않고 던전 수가 크지 않으므로, 백트래킹(bactracking, 퇴각검색) 알고리즘에 기반하여 문제를 해결하고자 했다.
구현
백트래킹에 기반하여 문제를 해결하기 위해 던전의 방문 여부를 표시할 배열(played[])을 별도로 선언하여 활용하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <vector>
using namespace std;
int Count;
void Play(int k, const vector<vector<int>>& dungeons, bool* const played, int idx, int cnt)
{
if (!played[idx] && k >= dungeons[idx][0])
{
played[idx] = true;
for (int i = 0; i < dungeons.size(); i++)
Play(k - dungeons[idx][1], dungeons, played, i, cnt + 1);
played[idx] = false;
}
else
{
if (Count < cnt)
Count = cnt;
}
}
int solution(int k, vector<vector<int>> dungeons)
{
for (int i = 0; i < dungeons.size(); i++)
{
bool played[8] = { 0, };
Play(k, dungeons, played, i, 0);
}
return Count;
}
실행 결과
'C++ 코딩 문제 풀이 > 프로그래머스' 카테고리의 다른 글
[Programmers] 구명보트 (1) | 2023.12.23 |
---|---|
[Programmers] 배달 (1) | 2023.12.21 |
[Programmers] 등굣길 (0) | 2023.12.19 |
[Programmers] 혼자 놀기의 달인 (0) | 2023.12.14 |
[Programmers] N-Queen (0) | 2023.12.12 |
댓글