99클럽 코테 스터디 39일차 TIL + 오늘의 학습 키워드

☑️ 문제:  광물 캐기

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

프로그래머스

 

☑️ 풀이

import java.util.*;

class Solution {
    int[][] energy = {
        { 1, 1, 1 },
        { 5, 1, 1 },
        { 25, 5, 1 }        
    };
    Map<String, Integer> mineralMap = new HashMap<>();
    
    int answer;
    
    public int solution(int[] picks, String[] minerals) {        
        // 1. init
        mineralMap.put("diamond", 0);
        mineralMap.put("iron", 1);
        mineralMap.put("stone", 2);        
            
        answer = Integer.MAX_VALUE;
        int totalPicks = 0;
        for (int i = 0; i < picks.length; i++) {
            totalPicks += picks[i];
        }
        
        // 2. dfs
        int[] usedPicks = new int[totalPicks];
        dfs(picks, minerals, usedPicks, totalPicks, 0);
        
        return answer;
    }
    
    void dfs(int[] picks, String[] minerals, int[] usedPicks, int totalPicks, int count) {
        if (count == totalPicks) {
            answer = Math.min(getTotalEnergy(minerals, usedPicks), answer);
        }
        
        for (int i = 0; i < picks.length; i++) {
            if (picks[i] > 0) {
                usedPicks[count] = i;
                picks[i]--;
                dfs(picks, minerals, usedPicks, totalPicks, count + 1);
                picks[i]++;
            }
        }
    }
    
    int getTotalEnergy(String[] minerals, int[] usedPicks) {
        int totalEnergy = 0;
        int usedPickIndex = 0;
        for (int i = 0; i < minerals.length; i += 5) {
            if (usedPickIndex >= usedPicks.length) {
                break;
            }
            
            for (int j = i; j < i + 5; j++) {
                if (j >= minerals.length) {
                    break;
                }
                int mineralIndex = mineralMap.get(minerals[j]);
                totalEnergy += energy[usedPicks[usedPickIndex]][mineralIndex];
            }
            usedPickIndex++;
        }
        return totalEnergy;
    }
}