프로그래머스 87946 - 피로도 (Lv.5)

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

// 프로그래머스 87946 - 피로도 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/87946
// (같은 백트래킹 골격: 백준 18429 근손실 — 전체 순열 + 제약 미달 시 가지치기, int 반환 dfs)

// 문제 설명
// 현재 피로도 k 로 던전을 탐험한다. 던전마다 "최소 필요 피로도"와 "소모 피로도"가 있고,
// 현재 피로도가 최소 필요 피로도 이상일 때만 입장할 수 있으며 입장하면 소모 피로도가 깎인다.
// 각 던전은 한 번만 탐험할 수 있고 순서는 자유롭게 정할 수 있다.
// 최대 몇 개의 던전을 탐험할 수 있는지 반환하라.

// 제약 조건
// 1 <= k <= 5,000
// 1 <= dungeons 길이 <= 8, dungeons[i] = [최소 필요 피로도, 소모 피로도]
// 1 <= 최소 필요 피로도, 소모 피로도 <= 1,000
// 최소 필요 피로도 >= 소모 피로도

// Example
// Input : k = 80, dungeons = [[80, 20], [50, 40], [30, 10]]
// Output: 3        ([80,20] → [30,10] → [50,40] 순서면 80 → 60 → 50 → 10 으로 셋 다 통과)

// 접근 — 순서를 전부 만들어 보는 백트래킹 (완전탐색)
//
// [1단계 — 그리디가 왜 틀리나]
// "최소 필요 피로도가 큰 것부터" 같은 기준을 세우고 싶어지지만, 예제가 그대로 반례다.
// 그 기준이면 [80,20] → [50,40] 으로 80 → 60 → 20 이 되어 [30,10] 이 막혀 답이 2가 된다.
// "소모 피로도가 작은 것부터"도 [30,10] 을 먼저 써 70이 되면 [80,20] 이 막혀 2가 된다.
// 남은 피로도가 다음 선택의 가능 범위를 바꾸는 구조라, 한 축의 정렬 기준으로 고정할 수 없다.
//
// [2단계 — 완전탐색으로 갈 수 있는 근거는 제약]
// 던전이 최대 8개니 모든 순서를 만들어도 8! = 40,320 가지. 판별법 로직도의 출발점인
// 브루트포스가 제약 안에서 그대로 통한다. 순서가 답을 바꾸므로 조합이 아니라 순열이다.
//
// [3단계 — visited 순열 백트래킹 + 제약 가지치기]
// N과 M (5)와 같은 골격: visited 로 이미 쓴 던전을 막고, 넣고 → 재귀 → 빼고를 대칭으로 둔다.
// 여기에 문제 제약을 가지치기로 얹는다 — k 가 최소 필요 피로도보다 작으면 그 가지는 버린다.
// 전체 순열을 다 만들고 나서 유효성을 검사하는 방식(next_permutation)보다 이쪽이
// 못 들어가는 순간 하위 순열 전체를 잘라내므로 실제 탐색량이 크게 줄어든다.
//
// [4단계 — "다 못 돌아도 답"이라 깊이 자체가 후보다]
// 8개를 모두 도는 것이 목표가 아니라 최대 개수를 구하는 문제다. 그래서 완성 지점에서만
// 값을 만드는 대신, 매 호출에서 int ret = depth 로 시작한다. 더 들어갈 던전이 없으면
// 그 깊이가 그대로 그 경로의 결과가 되고, 들어갈 수 있으면 자식의 결과와 max 를 취한다.
//
// 시간 O(n!) 최악 8! x n = 약 32만, 공간 O(n) (재귀 깊이 + visited)

#include <vector>
#include <algorithm>

using namespace std;

int n;
int visited[8];                      // 전역 선언 — 재귀 전반에서 공유. 던전 최대 8개

int dfs(vector<vector<int>>& dungeons, int k, int depth)
{
    int ret = depth;                 // 더 들어갈 던전이 없으면 지금 깊이가 이 경로의 결과

    for (int i = 0; i < n; i++)
    {
        if (visited[i]) continue;              // 같은 던전 재입장 금지
        if (k < dungeons[i][0]) continue;      // 최소 필요 피로도 미달 → 하위 순열 전체를 잘라낸다

        visited[i] = 1;                                              // 넣고
        ret = max(ret, dfs(dungeons, k - dungeons[i][1], depth + 1));
        visited[i] = 0;                                              // 빼고 (피로도는 인수라 복원 불필요)
    }

    return ret;
}

int solution(int k, vector<vector<int>> dungeons)
{
    n = (int)dungeons.size();
    for (int i = 0; i < n; i++) visited[i] = 0;

    return dfs(dungeons, k, 0);
}

정리

• 그리디 반례를 따로 만들 필요가 없다 — 공식 예제가 그대로 반례다. “최소 필요 피로도가 큰 것부터”로 정렬하면 [80,20] → [50,40]을 타면서 피로도가 20으로 떨어져 [30,10]이 막혀 2가 되고, “소모 피로도가 작은 것부터”로 정렬해도 [30,10]을 먼저 써 70이 되면 [80,20]이 막혀 2가 된다. 정답 3은 [80,20] → [30,10] → [50,40]이다. 남은 피로도가 다음 선택의 가능 범위를 바꾸므로 어떤 단일 정렬 기준도 최적을 보장하지 못한다 — 판별법 로직도의 “배열에 담기지 않으면 그리디” 갈래가 아니라, 애초에 브루트포스가 제약 안에서 통하는 경우다.
• 완전탐색으로 갈 근거는 제약 한 줄에 있다. 던전이 최대 8개라 모든 순서가 8! = 40,320가지. k <= 5,000이나 소모 <= 1,000이 아니라 던전 개수 8이 유형을 결정하는 제약이다. 그리고 순서가 답을 바꾸므로 조합(2⁸ = 256)이 아니라 순열을 만들어야 한다.
• 가지치기는 재귀 앞에 두는 것이 전부다. if (k < dungeons[i][0]) continue; 한 줄이 못 들어가는 던전의 하위 순열 전체를 잘라낸다. 순열을 다 생성하고 나서 유효성을 검사하는 next_permutation 방식은 항상 8!개를 전부 만들지만, 여기는 제약이 중간에 강하게 걸려 실제 탐색량이 훨씬 줄어든다. 순열 문제라고 무조건 next_permutation이 편한 것은 아니라는 갈림길.
• “완성 지점”이 없는 최대화 문제라 반환 골격이 달라진다. 18429 근손실은 ret_v.size() == n에서 1을 반환하는, 끝까지 갔을 때만 세는 구조였다. 여기는 8개를 다 돌지 못해도 그 깊이가 답의 후보이므로 int ret = depth;로 시작해 자식 결과와 max를 취한다. 끝까지 가야 답이면 완성 지점에서 1을 반환, 중간에 멈춰도 답이면 진입 시점의 깊이를 초기값으로 둔다.
• 되돌릴 상태와 넘길 상태를 구분하면 넣고/빼고가 짧아진다. visited는 배열이라 되돌려야 하지만(= 1 ↔ = 0), 피로도는 k - 소모로 인수로 넘기므로 호출이 끝나면 호출자의 k가 그대로 남아 복원 코드가 필요 없다. 1987 알파벳에서 마스크를 값으로 전달해 복원을 없앤 것과 같은 요령이다. 커리큘럼 93번.
• 검증: 예제(3)와 경계 케이스 — 피로도 부족으로 0개(k=1, [[10,10]] → 0), 딱 맞아 1개(k=10 → 1), 순서 무관하게 2개, 최대 입력 8개 던전 전부 [1000,1000]에 k=5000(→ 5) 통과 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — 그리디 정렬 기준을 세우려 할 필요가 없다. 공식 예제가 두 기준(“최소 필요 피로도 큰 것부터”, “소모 작은 것부터”) 모두에 대해 2를 내는 반례이고, 정답은 3이다. 던전이 최대 8개라 8! = 40,320가지 순열을 visited 백트래킹으로 전부 만들고 k < 최소 필요 피로도를 재귀 앞에서 잘라내면 된다. 다 돌지 못해도 그 깊이가 답의 후보라 int ret = depth;로 시작해 자식과 max를 취하는 것이, 완성 지점에서만 1을 반환하는 18429류와 갈리는 지점이다.