C# 광물 캐기 - DFS / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/172927

 

 

나의 코드

public int solution(int[] picks, string[] minerals) 
{
    int[,] pickCost = new int[3, 3]{ {1, 1, 1}, {5, 1, 1}, {25, 5, 1} };
    int[] mineralIndexs = new int[minerals.Length];
    for(int i = 0; i < minerals.Length; ++i)
    {
        switch(minerals[i])
        {
            case "diamond": mineralIndexs[i] = 0; break;
            case "iron": mineralIndexs[i] = 1; break;
            case "stone": mineralIndexs[i] = 2; break;
            default: break;
        }
    }

    int answer = int.MaxValue;
    DFS(picks, mineralIndexs, pickCost, 0, 0, ref answer);
    return answer;
}

private void DFS(int[] picks, int[] mineralIndexs, int[,] pickCost, int n, int fatigue, ref int answer)
{
    const int MAX_PICK = 5;

    if(n >= mineralIndexs.Length) // 광물을 다 캐버림
    {
        if(fatigue < answer)
            answer = fatigue;
    }

    bool isAnyPick = false;
    for(int i = 0; i < 3; ++i)
    {
        if(picks[i] == 0) continue;
        isAnyPick = true;

        int curFatigue = 0;
        for(int k = 0; k < MAX_PICK; ++k)
        {
            if(n + k >= mineralIndexs.Length) break;
            int mineIndex = mineralIndexs[n + k];
            curFatigue += pickCost[i, mineIndex];
        }

        --picks[i];
        DFS(picks, mineralIndexs, pickCost, n + MAX_PICK, fatigue + curFatigue, ref answer);
        ++picks[i];
    }

    if(!isAnyPick) // 곡괭이를 다 써버림
    {
        if(fatigue < answer)
            answer = fatigue;
    }
}

각 곡괭이의 수는 5개 이하로 경우의 수가 그리 많지 않기 때문에 DFS 재귀로 풀었다.

만약 곡괭이 수가 더 많은 문제라면 5개씩 묶어서 정렬하면 될 것이다.