지희의 고장난 계산기 [SWEA 1808][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AXCJQaIKch0DFAVg&contestProbId=AV4yC3pqCegDFAUx&probBoxId=AXCj60sq_jkDFAQK&type=PROBLEM&problemBoxTitle=3%EC%9B%9405%EC%9D%BC&problemBoxCnt=1

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

1. 거꾸로 생각해야한다.

2. 주어진 수를 계산기의 버튼으로 누를 수 있는지 검사한다.

3. 누를 수 없다면 주어진 수의 제곱근까지를 나눠본다.

4. 나누어 떨어지면서 버튼으로 누를 수 있다면 나눈 몫을 재귀함수로 호출한다.

5. 가장 최소 호출수인 dfs를 고른다.

import java.io.*;
import java.util.*;

public class 지희의고장난계산기 {
	public static int X;
	public static int min;
	public static boolean btn[];
	public static void main(String[] args) throws Exception{
		//입력
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine().trim());
		
		for (int tc = 1; tc < T; tc++) {
			min = Integer.MAX_VALUE;
			btn = new boolean[10];
			StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
			int num;
			for (int i = 0; i < 10; i++) {
				num = Integer.parseInt(st.nextToken());
				if(num == 1) {
					btn[i] = true;
				}
			}
			X = Integer.parseInt(br.readLine().trim());
			
			find(X,0);
			
			min = (min == Integer.MAX_VALUE)? -1 : min;
			System.out.println("#" + tc + " " + min);
		}
	
	}
	public static int find(int x, int cnt) {
		//basis case -> 종료조건
		if(isMake(x+"")) {
			//x값이 조어진 모든 수로 누를 수 있는 지 검사
			//x의 길이를 리턴
			if(cnt == 0) {
				min = len(x)+1;
			}
			return len(x) + 1;
		}
		//2~제곱근 까지 반복
		int result = -1;
		
		for (int i = 2, end = (int)Math.sqrt(x)+ 1; i < end; i++) {
			// i == x의 약수이며 true가 되어있는 값
			if(x % i==0 && isMake(i+"")) {
				// i의 길이를 구하고
				int len1 = len(i) + 1; // 곱하기 버튼을 위해 1을 더한다.
				// 몫이 x의 약수이면서 true가 되어있는 값
				int len2 = find(x/i , cnt + 1);
				
				if(len2 > -1) {
					//i의 길이와 몫의 길이를 + 
					result = len1 + len2;
					if(result < min && x == X) {
						min = result;
					}
				}
			}
		}
		return result;
	}
	public static boolean isMake(String x) {
		for(char c : x.toCharArray()) {
			if(!btn[c-'0']) {
				return false;
			}
		}
		return true;
	}
	public static int len(int x) {
		return (int)Math.log10(x) + 1;
	}
}