백준 12783번: 곱셈 게임

문제 설명

• https://www.acmicpc.net/problem/12783
• N개의 카드에서 곱셈을 최소한으로 이용해 주어진 숫자를 만들어야 합니다.

접근법

• 혼자서 해결하지 못해 다른분의 풀이를 참고해 풀었습니다.
• 숫자를 곱으로 표현하기 때문에 약수를 이용해 주어진 숫자를 만들 수 있습니다.
  (처음 틀릴때를 생각해보면 숫자를 기준으로 카드를 생각할지, 카드를 기준으로 숫자를 생각할지도 잘 판단해야 할 거 같습니다. 해당 풀이는 숫자를 기준으로 카드를 생각하는 방식으로 접근합니다.)
  이때 모든 약수를 구하는 게 아니라 Math.sqrt(K)까지의 약수만 활용해 시간 효율을 높였습니다.
• 또 하나 핵심은 어떤 숫자가 만들어지는지, 만들어 진다면 몇 개의 곱셈이 필요한지를 매번 계산하지 않고 메모이제이션을 활용해 시간을 단축시키는 것입니다.
• dp[i] = 숫자 i를 만들기 위해 최소한으로 사용한 곱셈의 수로 정의할 수 있습니다. 숫자 K에 대해 a*b = K가 성립하면 dp[K] = dp[a] + dp[b] + 1이 됩니다.
• 여러 다른 방법이 존재하겠지만 제 풀이에서 1과 K는 무한반복을 유발합니다. 이를 방지하기 위해 1에 대한 dp계산은 미리 진행하고 1에 대한 계산은 건너뛰었습니다. (1을 선택하지 않으면 K도 선택하지 않게 됩니다.)

기타

• 처음에는 크기가 1000001인 dp를 만들고 1부터 dp배열을 채우는 방법으로 접근했습니다.
  저에게 2와 3카드가 주어졌을 때 dp[2] = 0, dp[3] = 0, dp[4] = 1, dp[6] = 1, ... 을 채울 수 있다 생각했습니다. 하지만 506(22*23)을 계산하려면 모든 만들 수 있는 숫자를 다 확인해봐야 했기 때문에 이러한 방식으로 문제를 풀 수 없었습니다.

정답

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int[] arr = new int[N];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			int M = Integer.parseInt(br.readLine());
			int[] dp = new int[1000001];
			Arrays.fill(dp, Integer.MAX_VALUE);
			if(contains(1,arr)) {
				dp[1] = 0;
			}else {
				dp[1] = -1;
			}
			for (int i = 0; i < M; i++) {
				int K = Integer.parseInt(br.readLine());
				sb.append(findMultiplyCnt(K,dp,arr));
				sb.append("\n");
			}
		}
		System.out.println(sb.toString());
	}
	
	public static int findMultiplyCnt(int x, int[] dp, int[] arr) {
		// 이미 x를 계산한 적이 있다면 그대로 값을 반환
		if(dp[x] != Integer.MAX_VALUE) return dp[x];
		// 곱셈을 하지 않고 x를 만들 수 있다면
		if(canMakeWithoutMultiply(x,arr)) {
			dp[x] = 0;
			return dp[x];
		}else { // 곱셈을 이용해야 하는 경우
			List<Integer> lst = divisor(x);
			for (int i = 0; i < lst.size(); i++) {
				int num = lst.get(i);
				int pairNum = x/num;
				// 1은 건너뜀				
				if(num == 1) continue;
				if(dp[num] == Integer.MAX_VALUE) {
					dp[num] = findMultiplyCnt(num,dp,arr);
				}
				if(dp[pairNum] == Integer.MAX_VALUE) {
					dp[pairNum] = findMultiplyCnt(pairNum,dp,arr);
				}
				if(dp[num] == -1 || dp[pairNum] == -1) continue;
				dp[x] = Math.min(dp[x], dp[num] + dp[pairNum] + 1);
			}
			if(dp[x] == Integer.MAX_VALUE) {
				dp[x] = -1;
			}
			return dp[x];
		}
	}
	
    // 약수 찾기
	public static List<Integer> divisor(int x) {
		List<Integer> lst = new ArrayList<Integer>();
		for (int i = 1; i <= Math.sqrt(x); i++) {
			if(x%i == 0) {
				lst.add(i);
			}
		}
		return lst;
	}
	
	public static boolean canMakeWithoutMultiply(int x, int[] arr) {
		String s = Integer.toString(x);
		for (int i = 0; i < s.length(); i++) {
			if(!contains(s.charAt(i)-'0',arr)) return false;
		}
		return true;
	}
	
	public static boolean contains(int x, int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] == x) return true;
		}
		return false;
	}
	
}