[프로그래머스] 피로도

jh Seo·2023년 8월 17일

브루트 포스 프로그래머스 한번에 푼 문제

프로그래머스

목록 보기

24/33

개요

프로그래머스 : 피로도

문제 설명
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

접근 방식

각 던전을 모든 경우의 수로 탐험하며 제일 많은 던전을 탐험해야하는 문제다.
일단 DFS방식으로 모든 경우를 탐색했다.
방문 여부를 체크하는 bool형 배열을 선언해줬다.
```
bool visited[9];
```
던전의 최대갯수가 8개라서 넉넉히 잡아준다.

기본적인 원리는 던전의 사이즈 만큼 반복문을 통해 DFS를 하는 것이다.
재귀함수의 반환값은 해당 경로로 진입했을 때의 경로 레벨의 최대값을 반환한다.

int DFS(int curK, vector<vector<int>>& dungeons,int curDungeon, int level){
   //최소피로도 보다 현재 피로도가 더 작다면 현재 레벨 -1 리턴
   if(curK<dungeons[curDungeon][0]) return level-1;
   //레벨이 던전 크기라면 다 돌았음
   if(level==dungeons.size()) return dungeons.size();

   int ret=0;
   for(int i=0;i<dungeons.size();i++){
       if(visited[i]) continue;
       visited[i]=true;
       ret=max(ret,DFS(curK-dungeons[curDungeon][1],dungeons,i,level+1));
       visited[i]=false;
   }
   
   return ret;
}

던전 사이즈와 level을 비교하기 위해 level을 1부터 시작했다.
따라서 최소피로도보다 현재 피로도가 더 작아서 던전 진입을 못할 시
반환하는 level은 1을 감소해서 리턴해야한다.

전체 코드

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;
bool visited[9];
int DFS(int curK, vector<vector<int>>& dungeons,int curDungeon, int level){
    //최소피로도 보다 현재 피로도가 더 작다면 현재 레벨 -1 리턴
    if(curK<dungeons[curDungeon][0]) return level-1;
    //레벨이 던전 크기라면 다 돌았음
    if(level==dungeons.size()) return dungeons.size();

    int ret=0;
    for(int i=0;i<dungeons.size();i++){
        if(visited[i]) continue;
        visited[i]=true;
        ret=max(ret,DFS(curK-dungeons[curDungeon][1],dungeons,i,level+1));
        visited[i]=false;
    }
    
    return ret;
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    for(int i=0;i<dungeons.size();++i){
        if(visited[i]) continue;
        visited[i]=true;
        answer=max(answer,DFS(k,dungeons,i,1));
        visited[i]=false;
    }
    return answer;
}

생각

좀 헤멨던 부분은 DFS함수 처음에 조건문 두 개였다.
순서를 잘못 적어서

    //레벨이 던전 크기라면 다 돌았음
    if(level==dungeons.size()) return dungeons.size();
    //최소피로도 보다 현재 피로도가 더 작다면 현재 레벨 -1 리턴
    if(curK<dungeons[curDungeon][0]) return level-1;

처음에 이렇게 구현했었다.
이렇게되면 마지막 레벨에서 피로도가 부족해서 현재 던전에 진입을 못하는 데,
level이 던전 사이즈와 같은걸 먼저 체크해서 던전사이즈를 반환해버린다..
순서가 정말 중요한걸 다시 한번 깨우치는 시간이였다.

다른사람의풀이

다른 풀이들을 봤는 데, 이런 모든 경우의 수를 체크하는 문제에서
많은 분들이 next_permutation 함수를 사용하셨다.
do while문으로 사용되는데,

#include <algorithm>
#include <iostream>
#include <string>
 
int main()
{
    std::string s = "aba";
 
    do std::cout << s << '\n';
    while (std::next_permutation(s.begin(), s.end()));
 
    std::cout << s << '\n';
}

https://en.cppreference.com/w/cpp/algorithm/next_permutation
의 위 예제를 보면
do 안에 하고자하는 걸 구현하고 while에 next_permutation함수를 넣고 인자로 원하는 컨테이너의 처음과 끝을 넣어주는 방식이다.

위 예제의 결과는
aba
baa
aab
이렇게 나온다.

위 문제에 적용시키면 do문 안에
현재 나열된 던전들을 차례대로 통과하며 몇개의 던전을 통과할수 있나
체크하고 최대값을 갱신하는 식으로 구현하면 될것 같다.

jh Seo

코딩 창고!

이전 포스트

[프로그래머스] 카펫

다음 포스트

[프로그래머스] 피로도