N으로 표현

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.

맨 처음 생각한것
BFS로 숫자를 저장해서 풀어나간다면 해결할수있지 않을까? 가능해보인다 이 문제는 효율성을 따지지 않는다.
그런데 문제의 카테고리가 DP였기에 DP를 사용하여 풀었다.

N이 하나일때 가능한 조건 N
N이 둘일때 가능한 조건 N+N, N-N, NN, N/N, NN
N이 셋일때 가능한 조건 NN+N, NN-N, NNN, NN/N N+NN, N-NN, NNN, N-NN, NNN
N이 넷일때 가능한 조건 N+NNN, N-NNN... NN+NN, NN-NN... NNN/N, NNNN
따라서 점화식을 만들어보면
DP(n) = (DP(1) +-/ DP(n-1))+(DP(2) +-/ DP(n-2)).. (DP(n-1) +-/ DP(1))이다.

코드

import java.util.*;
class Solution {
    public int solution(int N, int number) {
    
        List<HashSet<Integer>> list = new ArrayList<>();
        //리스트 초기화 및 첫번째 리스트는 N이다.
        for(int i=0;i<9;i++){
            list.add(new HashSet());
        }
        list.get(1).add(N);
        
        if(N==number) return 1;
        
        for(int i=2;i<9;i++){
            HashSet<Integer> comp = list.get(i);
            for(int j=1;j<=i;j++){
                HashSet<Integer> A = list.get(j);
                HashSet<Integer> B = list.get(i-j);
                for(int pre : A){
                    for(int post : B){
                        comp.add(pre + post);
                        comp.add(pre - post);
                        comp.add(pre * post);
                        if(post!=0)
                            comp.add(pre / post);
                    }
                }
            }
            comp.add(Integer.parseInt(String.valueOf(N).repeat(i)));          
            if(comp.contains(number)){
                return i;
            }
        }
       
        return -1;
    }
}

DP문제는 점화식을 어떻게 만드느냐만 해결된다면 간단히 풀리는 문제같다.