프로그래머스(N으로 표현)

문제

코드

성공 코드

class Solution {
    private int staticN;
    private int staticNum;
    private int result = 9;

    public void dfs(int cnt, int number){
        if(staticNum == number || cnt > 8){
            result = Math.min(result, cnt);
            return;
        }

        int tmp = staticN;
        for (int i = 0; i < 8 - cnt; i++) {
            if(tmp > (staticN * staticNum)) return; 
            //불필요 탐색 제거
            
            dfs(cnt + i + 1, number + tmp);
            dfs(cnt + i + 1, number - tmp);
            dfs(cnt + i + 1, number * tmp);
            dfs(cnt + i + 1, number / tmp);
            tmp += (staticN * Math.pow(10, i + 1));
        }
    }
    
    public int solution(int N, int number) {
        staticN = N;
        staticNum = number;

        dfs(0, 0);
        return ((result == 9) ? -1 : result);
    }
}