SW아카데미 : 숫자게임

문제를 읽어보면 어떤숫자를 2~ n개로 나누엇을때 곱을 무한 반복하면서 가장 오랫동안 나눌 수 있는 경우는 

최대 몇번인지 구하는 방법이다.

 

처음에는 BFS로 접근해서 Queue가 터지는 경우가 생긴다.

 

그경우는 num 이라는 숫자를 a*b = c 라고 한다면 어느 가지에서 c의 중복이 몇번 일어날 수있다.

 

따라서 각각의 가지를 hashMap으로 기억해놧다가 알고 있는 값이라면 빠르게 반환하는게 중요하다.

 

그리고 비트마스크를 이용해서 어떤숫자를 조각 할수있다.

 

숫자의 길이가 len =4 라고한다면 

0000 // 아무것도 짜르지 않는경우 -> 이경우는 필요없으니 무시한다

0001 // 첫번째에 짜르는경우 ex 1234 를 1 234 로 나누는 경우다.

0101// 첫번째 3번째를 짜르는경우 1 23 4 로 나누는 경우다.

이렇게 생각한다면 몇개는 중복이 일어나지만 hashMap을 통해서 가지를 치기때문에 많은 시간복잡도가 나오지 않는다.

 

package 삼성;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class 숫자게임 {
	static int T;
	static long num;
	static HashMap<Long, Integer> hash = new HashMap<Long, Integer>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		StringBuffer sb = new StringBuffer();
		int turn;
		for (int t = 1; t <= T; t++) {
			num = Long.parseLong(br.readLine());
			sb.append('#').append(t).append(' ');
			// ------------------------------
			turn = dfs(num);
			// ------------------------------
			sb.append(turn);
			sb.append('\n');
		}
		System.out.println(sb.toString());
	}

	public static int dfs(long n) {
		if (n < 10)
			return 0;
		if (hash.containsKey(n)) {
			return hash.get(n);
		}
		String str = n + "";
		int len = str.length();
		int mvalue = 0;

		for (int i = 1; i < (1 << len); i++) {
			// 1인 순간에 컷 한다
			long next = 1;
			long th = 0;
			for (int j = 0; j < len; j++) {

				th = th * 10 + str.charAt(j) - '0';
				if ((i & (1 << j)) > 0) {
					// 컷
					next *= th;
					th = 0;
				}
			}
			if (th != 0)
				next *= th;
			if(next!=n)
				mvalue = Math.max(mvalue, dfs(next));
		}
		hash.put(n, mvalue+1);
		return mvalue+1;
	}
}