문제

문제링크

접근

• 재귀 구현은 항상 조금씩 애를 먹는 것 같다.
• 사칙연산의 모든 경우의 수를 탐색한다고 생각하면 구조를 이해하기 쉬워지다.

소스 코드

class Main {
    public static void main(String[] args) throws Exception {
        int N = 5;
        int number = 2;

        Solution sol = new Solution();
        System.out.println("result : " + sol.solution(N, number));
    }
}

class Solution {
    int answer = 9;
    int N = -1;
    int number = -1;

    public int solution(int N1, int number1) {
        N = N1;
        number = number1;

        cal(0, 0);
        return answer<9?answer:-1;
    }

    public void cal(int cnt, int currNum){
        if(currNum == number){
            answer = cnt;
            return;

        }
        else if(cnt >= answer) return;
         else {
            int op = N;
            for(int i = 0; i<8-cnt; i++ ) {
                cal(cnt+1+i, currNum+op);
                cal(cnt+1+i, currNum-op);
                cal(cnt+1+i, currNum*op);
                cal(cnt+1+i, currNum/op);

                op = (op*10)+N;
            }
        }
    }
}