선밥의 공부하는 블로그

광물 캐기

문제 링크

광물 캐기

분석

picks는 순서대로 다이아몬드, 철, 돌 곡괭이이며, 개수는 0 ~ 5개로 무작위입니다.
한 곡괭이는 최대 5개의 광물을 캘 수 있습니다.
한 번 사용한 곡괭이는 더 이상 사용할 수 없습니다.

minerals는 문자열 배열로, 채굴해야 할 광물들의 순서가 주어집니다.
각 요소는 "diamond", "iron", "stone"중 하나입니다.
광물은 주어진 순서대로만 캘 수 있습니다.

각 곡괭이로 광물을 캘 때 소모되는 피로도는 다음과 같습니다.

곡괭이 / 광물다이아몬드철돌
다이아몬드111
철511
돌2551

주어진 곡괭이로 광물을 채굴할 때, 필요한 총 피로도 중 가장 적은 값을 구해 반환하는 문제입니다.

주어지는 광물 배열을 5개씩 묶어 그룹을 만들고, 각 그룹에 대해 모든 곡괭이로 채굴했을 때의 피로도를 계산해주어 필요한 최소 피로도를 찾습니다.

그리디 알고리즘, DFS나 백트래킹을 사용한 완전탐색, DP로 풀 수 있습니다.

풀이

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

using namespace std;

// 곡괭이 별 피로도 테이블
// fatigue[곡괭이 타입][광물 타입] = 소모 피로도
// 각각 다이아몬드, 철, 돌
int fatigue[3][3] = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}}; 

// 최소 피로도 값을 저장할 전역 변수
int answer = INT_MAX;

// 광물 이름을 인덱스로 변환하는 함수
int getMineralIndex(const string& m)
{
    if (m == "diamond")
    {
        return 0;        
    }
    else if (m == "iron")
    {
        return 1;
    }
    return 2;
}

// DFS를 사용해서 모든 곡괭이 사용 순서 조합을 탐색한다.
// picks: 남은 곡괭이 수
// minerals: 채굴할 광물 목록
// index: 현재 인덱스로 다음에 채굴할 광물 시작 인덱스를 의미한다.
// currentFatigue: 현재까지 누적된 피로도
void dfs(vector<int> picks, const vector<string>& minerals, int index, int currentFatigue)
{
    // 종료 조건으로 광물을 전부 채굴했거나 곡괭이를 다 쓴 경우
    if (index >= minerals.size() || (picks[0] + picks[1] + picks[2]) == 0)
    {
        // 최소 피로도를 구한다.
        answer = min(answer, currentFatigue);
    }
    
    // 사용할 곡괭이 종류를 순회
    for (int i = 0; i < 3; ++i)
    {
        // 현재 순회된 곡괭이가 없는 경우
        if(picks[i] == 0)
        {
            continue;
        }
        
        // 재귀 호출 시 원본을 보존하기 위해 곡괭이 수 복사
        vector<int> tempPicks = picks;

        // 복사된 곡괭이 하나 사용
        --tempPicks[i];
        
        // 이번 묶음에 대해 소모할 피로도 합계
        int fatigueSum = 0;
        
        // 이번 곡괭이로 채굴할 최대 5개의 광물 범위 계산
        int end = min(index + 5, static_cast<int>(minerals.size()));
        // index 부터 end - 1까지 채굴하면서 피로도 계산
        for (int j = index; j < end; ++j)
        {
            // 광물 인덱스를 구한다.
            int mIndex = getMineralIndex(minerals[j]);
            // 해당 곡괭이로 채굴 시 피로도 누적
            fatigueSum += fatigue[i][mIndex];
        }
        
        // 다음 묶음 탐색
        // 인덱스를 5 증가시키고, 누적 피로도를 갱신한다.
        dfs(tempPicks, minerals, index + 5, currentFatigue + fatigueSum);
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    // 모든 곡괭이로 채굴할 수 있는 최대 광물 수
    // 곡괭이 하나당 최대 5개를 채굴 할 수 있으므로 * 5
    int maxMineCount = (picks[0] + picks[1] + picks[2]) * 5;
    
    // 광물 개수가 채굴 가능 개수보다 많으면 초과 부분 제거
    if (minerals.size() > maxMineCount)
    {
        minerals.resize(maxMineCount);
    }
    
    dfs(picks, minerals, 0, 0);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(p!)$입니다.

  • DFS에서 곡괭이 사용 순서를 모두 탐색 $O(p!)$
    • p는 총 곡괭이 수
  • DFS에서 호출당 최대 5개의 광물에 대한 피로도 계산 $O(5)$
  • $O(p!) \times O(5)$

공간 복잡도는 $O(p)$입니다.

  • DFS의 재귀 호출 스택 깊이 $O(p)$

테스트 1 〉 통과 (0.02ms, 4.21MB)
테스트 2 〉 통과 (211.67ms, 3.71MB)
테스트 3 〉 통과 (0.01ms, 3.67MB)
테스트 4 〉 통과 (0.02ms, 4.19MB)
테스트 5 〉 통과 (0.02ms, 4.22MB)
테스트 6 〉 통과 (0.03ms, 3.68MB)
테스트 7 〉 통과 (0.02ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.13MB)
테스트 9 〉 통과 (0.01ms, 4.19MB)
테스트 10 〉 통과 (0.01ms, 4.13MB)
테스트 11 〉 통과 (1.83ms, 4.2MB)
테스트 12 〉 통과 (0.41ms, 3.66MB)
테스트 13 〉 통과 (0.11ms, 4.14MB)
테스트 14 〉 통과 (0.75ms, 4.21MB)
테스트 15 〉 통과 (0.19ms, 3.71MB)
테스트 16 〉 통과 (0.01ms, 4.13MB)
테스트 17 〉 통과 (0.01ms, 4.21MB)
테스트 18 〉 통과 (0.01ms, 4.14MB)
테스트 19 〉 통과 (0.01ms, 4.19MB)
테스트 20 〉 통과 (0.92ms, 4.17MB)
테스트 21 〉 통과 (0.91ms, 4.27MB)
테스트 22 〉 통과 (165.84ms, 4.13MB)
테스트 23 〉 통과 (165.20ms, 4.19MB)
테스트 24 〉 통과 (219.97ms, 4.21MB)
테스트 25 〉 통과 (171.24ms, 4.24MB)
테스트 26 〉 통과 (1.15ms, 4.12MB)
테스트 27 〉 통과 (0.80ms, 4.21MB)
테스트 28 〉 통과 (0.12ms, 4.2MB)
테스트 29 〉 통과 (1.04ms, 4.17MB)
테스트 30 〉 통과 (312.04ms, 3.68MB)
테스트 31 〉 통과 (164.38ms, 4.2MB)
테스트 32 〉 통과 (178.20ms, 3.67MB)
테스트 33 〉 통과 (184.50ms, 4.21MB)
테스트 34 〉 통과 (164.27ms, 4.13MB)
테스트 35 〉 통과 (176.55ms, 4.2MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글