[프로그래머스][N으로 표현]-Lv.3

🎉 문제

문제링크

🎉 제한사항

🎉 접근방법

1. DFS을 통해 +, -, /, * 를 통해 해당 값을 찾았을 때 cnt의 최솟값을 구한다.
2. 만약 처음 최솟값으로 설정한 Integer.MAX_VALUE라면 -1 리턴

🎉 코드

class Solution {
    static int answer = Integer.MAX_VALUE;
    static int n,num;
    public int solution(int N, int number) {
        n = N;
        num = number;
        dfs(0,0);
        return answer==Integer.MAX_VALUE?-1:answer;
    }
    static void dfs(int cnt, int cur){
        if(cnt > 8){
            return;
        }        
        if(cur == num){
            answer = Math.min(answer,cnt);
            return;
        }
        int temp = n;
        for(int i=0; i<8; i++){
            dfs(cnt+i+1, cur + temp);
            dfs(cnt+i+1, cur - temp);
            dfs(cnt+i+1, cur / temp);
            dfs(cnt+i+1, cur * temp);
            
            temp = temp * 10 + n;
        }
    }
}