[DP] - N으로 표현

 

 

DP란?

• 중복 계산을 피하고, 작은 문제를 해결하여 큰 문제를 해결해 나가는 방식

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        int answer = -1;
        Set<Integer>[] set = new Set[9];
        
        int t = N;
        
        //최솟값이 8보다 크면 -1 리턴
        for(int i=1;i<9;i++){
            set[i] = new HashSet<>();
            set[i].add(t);
            t = t*10+N;

            for(int j=1;j<i;j++){
                for(int a: set[j]){
                    for(int b: set[i-j]){
                        set[i].add(a+b);
                        set[i].add(a-b);
                        set[i].add(a*b);
                        if(a!=0){
                            set[i].add(b/a);
                        }
                    }
                }
            }
                 
            if(set[i].contains(number)){
                return i;
            }
        
        }
        return answer;
    }
}