[프로그래머스] 피로도 | C++

문제

프로그래머스

 

나의 풀이 전략

방문할 던전을 나열하는 방법은 두가지로 보인다.

1) DFS로 풀어본다.

2) next_permutation()을 이용해본다. (여기서 설명할 방법)

 

DFS로 한다면, 방문체크가 필요할 것이다.

그러면 풀이자들은 던전에 방문했는지를 체킹하기 위해 별도의 선형 자료구조를 구성해야 한다.

그런데, DFS로 함수 인수를 구성하기, 방문 체킹-언체킹, 제약조건에 따르기 등

내가 직접 방문순서를 관리하는건 솔직히 귀찮고 힘들기도 하다.

 

나는 그래서 2번째로 풀때는

next_permutation() 함수를 이용해서 풀어봤고,

훨씬 더 깔끔한 코드가 나왔다고 생각했다.

이전 소스코드와 비교할 때

별도의 DFS 함수 필요없이 방문순서를 구성하는 건 굉장한 매력이 있다.

 

상세

1. 던전을 방문할 순서를 나열한 vector<int> orders를 선언해준다.

그리고 dungeons의 크기만큼 순서를 넣어준다.

int answer; // 우리가 제출할 정답

int solution(int k, vector<vector<int>> dungeons)
{
    vector<int> orders;

    for(int i = 0; i < dungeons.size(); ++i)
        orders.push_back(i);
}

 

2. next_permutation()으로 orders를 완전탐색한다.

(checking DFS보다 훨씬 간편한 방법 아닌가! 가끔은 모든 제어를 내가 안하는 것이 더 낫다.)

int solution(int k, vector<vector<int>> dungeons)
{
    // ...

    do
    {

    }
    while (next_permutation(orders.begin(), orders.end()));
}

 

여기서 잠깐, while 문이 아닌 do-while 문으로 해줘야 하는 이유는?

while 문에서 next_permutation()으로 호출되면,

orders는 처음상태가 아닌, 한번 next_permuation()이 이루어진 상태부터 시작한다.

즉, 모든 경우의 수에서 2번째 경우부터 탐색하는 꼴이 된다.

이를 방지하기 위해 do-while 문으로 돌려야 한다.

 

3. 구성된 orders에 따라 던전을 순차적으로 탐색한다.

문제의 제약조건에 따라 던전을 통과하면 갯수를 더해준다 (cnt++).

더해준 갯수(cnt)와 answer를 비교해가면서 answer를 갱신시켜주자.

do
{
    int hp = k;
    int cnt = 0;

    for(int order : orders)
    {
        int need = dungeons[order][0];
        int consume = dungeons[order][1];

        if(hp >= need)
        {
            hp -= consume;
            cnt++;
        }
        else break;
    }

    answer = max(answer, cnt);
}
while (next_permutation(orders.begin(), orders.end()));

 

전체 소스코드

#include <algorithm> // next_permutation
#include <string>
#include <vector>
#include <iostream>
using namespace std;

int answer = 0;

int solution(int k, vector<vector<int>> dungeons)
{
    vector<int> orders;

    for(int i = 0; i < dungeons.size(); ++i)
        orders.push_back(i);

    do
    {
        int hp = k;
        int cnt = 0;

        for(int order : orders)
        {
            int need = dungeons[order][0];
            int consume = dungeons[order][1];

            if(hp >= need)
            {
                hp -= consume;
                cnt++;
            }
            else break;
        }

        answer = max(answer, cnt);
    }
    while (next_permutation(orders.begin(), orders.end()));

    return answer;
}

int main()
{
    cout << solution(80, {{80, 20}, {50, 40}, {30, 10}});
    return 0;
}

 

이전 소스코드 — DFS 풀이

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int len;
bool check[8];

int answer;

void DFS(int k, int L, vector<vector<int>>& dungeons) {
	
    if(L == len)
    {
        answer = len;
        return;
    }

    for(int i = 0; i < len; i++)
    {
        if(check[i] == false) {
            if(k >= dungeons[i][0])
            {
                check[i] = true;
                DFS(k - dungeons[i][1], L + 1, dungeons);
                answer = max(answer, L + 1);
                check[i] = false;
            }
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    len = dungeons.size();

    DFS(k, 0, dungeons);

    return answer;
}

int main() {
    return 0;
}