지희의 고장난 계산기

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yC3pqCegDFAUx&categoryId=AV4yC3pqCegDFAUx&categoryType=CODE

SW Expert Academy

알고리즘

1. 재귀함수를 사용한다.

종료 조건은 주어진 값을 버튼으로 누를 수 있으면 숫자의 길이 + 1(=버튼) 종료된다.

가치치기는 min보다 커지면 return한다.

 

2. 누르지 못한다면 input값의 약수를 찾는다.

약수는 버튼으로 누를 수 있어야 한다. 약수를 찾았다면 몫과 약수의 길이 + 1(x버튼)을

재귀호출한다.

주의사항

1. 곱하기를 하지 않아도 식이 완성 될 수 있다.

ex) 1 2 4 8 버튼을 누를 수 있다면 1248을 구하는데는 1248 = 1248 하면 된다.

 

구현

class Solution_지희의고장난계산기2
{
    static boolean btn[];
    static int result;
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            btn = new boolean[10];
            StringTokenizer s =new StringTokenizer(in.readLine()," ");
            for (int i = 0; i < 10; i++) {
                if(Integer.parseInt(s.nextToken()) == 1)
                    btn[i] = true;
            }
            int input = Integer.parseInt(in.readLine().trim());
            result = Integer.MAX_VALUE;
            DFS(input,0);
            System.out.println("#"+test_case+" "+(result==Integer.MAX_VALUE ? -1:result));
        }
    }
    private static void DFS(int x,int cnt) {
        //종료조건
        if(check(x+"")) //int인 x가 string으로 들어감
        {
            cnt+=len(x)+1; //=버튼 포함
            if(result > cnt)
                result=cnt;
            return;
        }
        else if(result < cnt)
            return;
        //종료가 아닐때
        for (int i = 2; i < Math.sqrt(x); i++) {
            if(check(i+"") && x%i == 0) //x의 약수를 구함 약수는 누를 수 있는 버튼이여야 하고 약수여야함
            {
                DFS(x/i,cnt+len(i)+1);
            }
        }
    }
    private static int len(int x) {
        return (int) Math.log10(x)+1; //log10하면 숫자의 길이가 구해짐
    }
    private static boolean check(String s) { //버튼으로 누를 수 있는지 체크
        for (int i = 0; i < s.length(); i++) {
            if(!btn[s.charAt(i)-'0'])
                return false;
        }
        return true;
    }
}