N으로 표현

 

import java.util.HashSet;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>> result = new ArrayList<>();
        for(int i=0; i<=8; i++){
            result.add(new HashSet<>());
        }
        result.get(1).add(N); //N을 1개만 쓰는 경우
        
        for(int i=1; i<=8; i++){
            Set<Integer> set = result.get(i); //현재 set
            set.add(Integer.parseInt(String.valueOf(N).repeat(i)));
            
            for(int j=1; j<i; j++){ //이전 set들 사칙연산
                for(int left : result.get(j)){
                    for(int right : result.get(i-j)){
                        set.add(left+right);
                        set.add(left-right);
                        set.add(left*right);
                        if(right!=0) set.add(left/right);
                    }
                }
            }
            
            if(set.contains(number)) return i;   
        }
        return -1;
    }
}

 

전에 dfs로 풀었다가 명색이 dp 문젠데 ....라 해서 다시 풀었다.

result에 set이 들어가게되는데

index가 1인 경우가 N이 1개인 경우,

index가 2인 경우가 N이 2개인 경우 .... 

로 index를 바로 이용하기 위해 0은 빈공간으로 만들어주었다.