🖋️ 광물 캐기

# 문제 설명

곡괭이로 광산에서 규칙을 지키면서
최소한의 피로도로 광물을 캐기

• 조건
  

  • 사용할 수 있는 곡괭이중 하나를 선택해 광물을 캐기
  • 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용
  • 광물은 주어진 순서대로만 가능
  • 광산에 있는 모든 광물을 캐거나
    더 사용할 곡괭이가 없을 때까지 광물을 캐기
    
    
  • 피로도 소모

    • 	다이아	철	돌
      다이아	1	1	1
      철	5	1	1
      돌	25	5	1

      
      
  • 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용 불가능

• 매개 변수
  

  • 마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks
  • 광물들의 순서를 나타내는 문자열 배열 minerals

• 반환값
  

  • 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return

• 📢 제한사항

  • picks는 [dia, iron, stone]

    • 0 ≤ dia, iron, stone ≤ 5
    • dia : 다이아몬드 곡괭이의 수
    • iron : 철 곡괭이의 수
    • stone : 돌 곡괭이의 수
    • 곡괭이는 최소 1개 이상
    
    

  • minerals는 다음 3개의 문자열

    • diamond : 다이아몬드
    • iron : 철
    • stone : 돌

• 📰 입출력 예시

picks	minerals	result
[1, 3, 2]	["diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"]	12
[0, 1, 1]	["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"]	50

• CODE

function solution(picks, minerals) {
    let answer = 25 * minerals.length;
    
    const dfs = (p_arr, m_arr, fatigue) => {
        if (p_arr.every(v => v === 0) || !m_arr.length) {
            answer = Math.min(answer, fatigue);
            return;
        }
        
        const [dia, iron, stone] = p_arr;
        
        // 다이아 곡괭이 있을 때
        if (dia > 0) {
            const nextP = [dia-1, iron, stone];
            const nextM = m_arr.slice(5);
            const nextF = fatigue + (m_arr.length - nextM.length);
            dfs(nextP, nextM, nextF);
        }    
        
        let countM = [0, 0, 0];
        m_arr.slice(0, 5).forEach((v) => {
            if (v === "diamond") countM[0] += 1;
            else if (v === "iron") countM[1] += 1;
            else countM[2] += 1;
        });

        // 철 곡괭이 있을 때
        if (iron > 0) {
            const nextP = [dia, iron-1, stone];
            const nextM = m_arr.slice(5);
            const nextF = fatigue + (countM[0] * 5 + countM[1] + countM[2]);
            dfs(nextP, nextM, nextF);
        }    
        
        // 돌 곡괭이 있을 때
        if (stone > 0) {
            const nextP = [dia, iron, stone-1];
            const nextM = m_arr.slice(5);
            const nextF = fatigue + (countM[0] * 25 + countM[1] * 5 + countM[2]);
            dfs(nextP, nextM, nextF);
        }    
    }
    
    dfs(picks, minerals, 0);
    
    return answer;
}

풀이

• DFS 완전 탐색을 통해 solution 구하기
  
  
• answer 은 피로도의 최솟값을 담기 위해
  반환 가능한 피로도 최댓값으로 초기화
  
  
• 주어진 광물에 순서대로 광물을 캐고
  조건에 따라 피로도가 달리 발생하고
  최솟값을 구하기 때문에 완전 탐색
  
  
• 탐색을 종료하는 조건
  • 곡괭이가 고갈될 때
  • 광석을 모두 캤을 때
    
    
• 각각 곡괭이로 캤을 때 DFS 탐색

• 성능 더 좋은 다른 사람 풀이 (그리디)

function solution(picks, minerals) {
    const remainPicks = [...picks];
    const maxFatigue = [];
    const useable = minerals.slice(0, picks.reduce((acc, cur) => acc + cur) * 5);
  
  useable.forEach((mineral, index) => {
        if (index % 5 === 0) maxFatigue.push({"diamond": 0, "iron": 0, "stone": 0});
        maxFatigue.at(-1)[mineral] ++;
    })
  
  maxFatigue.sort((a, b) => (b.diamond * 25 + b.iron * 5 + b.stone) - (a.diamond * 25 + a.iron * 5 + a.stone))
  
    const answer = maxFatigue.reduce((acc, {diamond, iron, stone}) => {
        if (remainPicks[0] !== 0) {
            remainPicks[0] --;
            return acc + diamond + iron + stone;
        } else if (remainPicks[1] !== 0) {
            remainPicks[1] --;
            return acc + diamond * 5 + iron + stone;
        } else {
            remainPicks[2] --;
            return acc + diamond * 25 + iron * 5 + stone;
        }
    }, 0)
    return answer;
}