[프로그래머스][JAVA] N으로 표현

programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

동적계획법 카테고리에 있었지만 dfs을 통해 풀었다.

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