import java.util.*; public class PotionBrewer { private static final Map<String, List<List<String>>> recipes = new HashMap<>(); private static final Map<String, Integer> memoization = new HashMap<>(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int numRecipes = scanner.nextInt(); scanner.nextLine(); for (int i = 0; i < numRecipes; i++) { String[] recipeParts = scanner.nextLine().split("="); String potion = recipeParts[0].trim(); String[] ingredients = recipeParts[1].split("\\+"); recipes.computeIfAbsent(potion, k -> new ArrayList<>()).add(Arrays.asList(ingredients)); } String targetPotion = scanner.nextLine(); scanner.close(); int result = calculateMinimumOrbs(targetPotion); System.out.println(result); } private static int calculateMinimumOrbs(String potion) { if(!recipes.containsKey(potion)){ return 0; } if(memoization.containsKey(potion)){ return memoization.get(potion); } int minOrbs = Integer.MAX_VALUE; for (List<String> recipe : recipes.get(potion)){ int orbsRequired = recipe.size() - 1; for(String ingredient : recipe){ orbsRequired += calculateMinimumOrbs(ingredient); } minOrbs = Math.min(minOrbs, orbsRequired); } memoization.put(potion, minOrbs); return minOrbs; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter