프로그래머스 - 피로도 (C++)

문제 링크입니다.

프로그래머스

---

일단 확인해야 할 내용은 데이터 크기입니다. 던전의 개수가 최대 8개네요. 이런 경우에는 효율적인 탐색을 고려하지 않아도 웬만하면 타임오버가 발생하지 않습니다. 이런 정보를 바탕으로 2가지 방법으로 문제를 풀어보겠습니다.

---

순열

int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    int currentK = k;
    sort(dungeons.begin(), dungeons.end());
    
    do {
        int sum = 0;
        currentK = k;
        for(int i = 0; i < dungeons.size(); i++) {
            if(dungeons[i][0] <= currentK) {
                currentK -= dungeons[i][1];
                sum++;
                if(sum == dungeons.size()) return sum;
            }
        }
        answer = max(sum, answer);
    } while (next_permutation(dungeons.begin(), dungeons.end()));
    
    return answer;
}

next_permutation을 사용하기 위해 dungeons를 초기에 sort해줍니다.

그리고 do-while문을 사용해서 dungeons를 가능한만큼 탐색합니다.

이때 sum == dungeons.size()라면 (=모든 던전을 다 탐색할 경우를 찾았다면) 바로 sum을 리턴시키면서 함수를 종료시켜줘도 됩니다.

그게 아니라면 반복문 종료시 현재 최대로 저장된 탐색횟수(answer)와 비교하여 최대값을 업데이트 해줍니다.

 

이렇게 모든 순열을 do-while로 순회하고, 순회가 끝나면 answer를 리턴해주면 됩니다.

 

---

DFS

bool visited[8] = {};
int maxDepth = 0;

void dfs(int depth, int k, vector<vector<int>>& dungeons) {
    maxDepth = max(maxDepth, depth);
    
    for(int i = 0; i < dungeons.size(); i++) {
        if(visited[i] || dungeons[i][0] > k) continue;
        
        visited[i] = true;
        dfs(depth+1, k-dungeons[i][1], dungeons);
        visited[i] = false;
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    dfs(0, k, dungeons);
    return maxDepth;
}

dfs함수를 하나 만듭니다.

maxDepth는 최대로 탐색한 던전의 개수이며, dfs함수의 호출시점마다 업데이트 해줍니다(그래도 되기때문에).

 

이후 for문을 돌면서

1. 방문한 던전은 패스

2. 방문하지 않은 던전은 방문처리후 그상태로 dfs실행(이때 (depth+1)과, (현재 k값 - i던전의 소모피로도)를 인자로 넣어줍니다).

3. i를 방문처리하면서 돌렸던 dfs가 모두 종료되면 i에 대한 방문처리를 다시 해제합니다.

그럼 모든 경우를 돌아볼 수 있습니다.

 

solution함수에서는 dfs(0,k,dungeons);를 실행해주면 전역변수인 maxDepth가 업데이트 될겁니다. 그대로 리턴해주면 됩니다.