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

1.문제 링크

피로도

2. 풀이 전 계획과 생각

• DP

3. 풀이

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

// 최소피로도, 소모피로도
int solution(int k, vector<vector<int>> dungeons) {
    vector<int> v;
    for (int i = 0; i <dungeons.size(); i++) v.push_back(i);

    int maxCnt= 0;

    do {
        int remainK = k;
        int cnt = 0;
        for (int i = 0; i < v.size(); i++) {
            int demandHealth = dungeons[v[i]][0];
            int usedHealth = dungeons[v[i]][1];
            if (demandHealth > remainK) continue;
            remainK -= usedHealth; 
            cnt++;
        }
        maxCnt = max(maxCnt, cnt);
    } while (next_permutation(v.begin(), v.end()));
    return maxCnt;
}

dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하이기 때문에 순열을 이용해 모든 경우의 수를 구한다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감

• 문제 조건을 처음에 읽어야 한다는 점을 깨달음. 처음에 문제 조건을 읽었다면, 처음부터 순열로 문제를 풀었을 것 같다

• 순열에 대해 복습할 수 있어 유익했다.