문제 87946. 피로도

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

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

입력

• 유저의 현재 피로도 k
• 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons

입력 제한

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입력 예제

// input
80			  // k
[[80,20],[50,40],[30,10]] // dungeons

// ans
3

 

풀이 방식

이 문제를 푸는 방식은 다양하겠지만, 본인은 dfs를 사용했다. 이유는 이러하다.

 

최소 필요 피로도의 존재

각 던전을 들어가는데 조건이 소모 피로도만 있었다면 오름차순으로 정렬해 소모 피로도가 작은 것부터 탐험해 갯수를 구하면 되었을 것이다. 하지만, 최소 필요 피로도가 존재하는한, [10^9, 1]과 같이 최소 필요 피로도가 엄청 높고, 소모 피로도가 엄청 낮은 경우에는 정렬했을 때 가장 앞에 있음에도 탐험할 수 없다. 따라서, 다른 방법이 필요했다.

 

최대 던전의 개수가 매우 작다

이 문제의 특이점은 던전의 개수가 8개로 매우 작다는 것이다. 완전 탐색(8!)을 구해도 시간 초과의 한계 연산 횟수인 1억번 과는 한참 거리가 멀다. 따라서, 브루트 포스를 하든, 완전 탐색 방식(DFS, BFS)을 하든 전혀 문제가 되지 않았다. 그렇다면 구현했을 때 코드 로직이 문제와 위화감이 없고 구현하기 쉬운 방법이 뭐가있을까 고민하다 최종적으로 DFS를 선택했다. 

 

정답 코드 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int K;
vector<vector<int>> dungeons_global;
vector<bool> visited;
vector<int> order;
int ans = 0;
void dfs(int size){
    
    if(size == dungeons_global.size()){
        int left_k = K;
        int cnt = 0;
        for(int elem : order){
            if(left_k < dungeons_global[elem][0]) break;
            
            cnt++;
            left_k -= dungeons_global[elem][1];
        }
        
        ans = max(ans, cnt);
        
        return;
    }
    
    for(int i = 0; i < dungeons_global.size(); i++){
        if(!visited[i]){
            visited[i] = true;
            order.push_back(i);
            
            dfs(size+1);
            
            visited[i] = false;
            order.pop_back();
        }
    }
    return;
}

int solution(int k, vector<vector<int>> dungeons) {
    K = k;
    int answer = -1;
    int dungeons_size = dungeons.size();
    visited.resize(dungeons_size);
    dungeons_global = dungeons;
        
    dfs(0);
    
    answer = ans;
    
    return answer;
}