[1일 1알고] Lv2 힌트 스테이지

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

프로그래머스

BOJ가 문을 닫는다니 아쉬운 일이네요

오늘부터는 다른 사이트들에서도 문제를 풀어가려고 합니다.

// 1->n개의 스테이지 해결 필요
// 스테이지 해결을 위해서는 비용 필요, 힌트권 사용시 비용 감소
// i번 힌트권은 i번에서 사용 가능
// 한 스테이지에서 힌트권은 n-1개 사용 가능

// 힌트 번들을 최대 1개 구매 가능
// 힌트 번들은 이후 스테이지의 힌트권 제공

// 입력 cost = 각 스테이지의 힌트권 사용 수에 따른 해결비용
// hint = 구매 가능한 번들 비용[0], 구매하는 힌트권 번호[1~N]

 

프로그래머스처럼 실제 기업들의 코딩 테스트와 가까운 문제는 지문과 조건을 보고 이해하는 것이 비중이 높습니다.

특히 이 문제는 카카오 기출문제이기도 하네요

 

n의 길이 = cost의 길이가 16이하이며, hint의 길이는 n-1이며, hint[i]의 길이는 2이상, 20이하이기 때문에 

 

2^(n-1)번의 계산이면 완전탐색이 가능합니다. 2^15면 대략 32000이고, 대충 1억번의 루프를 1초라고 잡으면 시간은 넉넉할 것으로 보입니다.

---

탐색의 기준은 특정 힌트번들을 포함했는지 안했는지 입니다.

bool타입 배열 혹은 vector를 사용해 dfs로 백트래킹하는 것도 괜찮지만

 

좀 더 간단하게 재귀없이 루프를 타고자, 비트마스킹을 사용했습니다.

 

대부분 아시겠지만 0~(2^M)-1 까지 탐색하면 0, 1, 10, 11, 100 처럼 증가하며 모든 경우를 확인할 수 있습니다.

#include <string>
#include <vector>
#include <climits>

using namespace std;

int solution(vector<vector<int>> cost, vector<vector<int>> hint) {
    int N = cost.size();
    int M = hint.size();
    int mask = 1 << M;
    long long answer = LLONG_MAX;
    for (int m = 0; m < mask; ++m)
    {
        long long result = 0;
        vector<int> hint_cnt(N, 0);
        for (int i = 0; i < M; ++i)
        {
            if ((m >> i) & 1)
            {
                for (int j = 1; j < hint[i].size(); ++j)
                {
                    ++hint_cnt[hint[i][j] - 1];
                }
                result += hint[i][0];
            }
        }
        for (int i = 0; i < N; ++i)
        {
            result += cost[i][min(hint_cnt[i], N - 1)];
        }
        answer = min(answer, result);
    }

    return answer;
}

 

여기서 실수가 있을 수 있는 점은 힌트권의 번호는 1-index이지만 주어지는 vector자체는 0-index로 주어지기 때문에 이를 고려해야합니다.

물론 테스트 케이스 실행에서 잡히긴 하겠네요