Programmers N으로 표현

●문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=java

●정리(요약)
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

●코드

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int N, int number) {
        Set<Integer>[] dp = new HashSet[9];

        for (int i = 1; i <= 8; i++) {
            dp[i] = new HashSet<>();
            
            int num = 0;
            for (int k = 0; k < i; k++) {
                num = num * 10 + N;
            }
            dp[i].add(num);

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

            if (dp[i].contains(number)) {
                return i;
                
            }
        }

        return -1;
    }
}

●느낀 점

처음은 숫자기준으로 dp[값(number)] 으로 하였다 왜냐하면,

dp[1] = 2 (5/5) = (1/1) 
dp[2] = 3 (5+5)/5 = (1+1)/1 
dp[3] = 4 (5+5+5)/5 
dp[4] = 5 (5+5+5+5)/5 
dp[5] = 1 
dp[6] = 3 5+(5/5) = 5+1 = 5+dp[1] = 3 
dp[7] = 4 5+2 = dp[5]+dp[2] = 1+3 
dp[11] = 3 55/5 = 11/1 
dp[12] = 5+7 = dp[5] +dp[7] = 1+4 Math.min(dp[5]+dp[7], 함수);

이런식으로 생각해서 dp[i] = dp[N] + dp[N-i] 라고 생각하고 Math.min(dp[i] , 함수(55/5 같은 55라는 수가 나오도록하는 함수)) 를 생각했지만, 잘못되었다.

그래서 개수 기준으로 생각했다.
dp[1] = 5
dp[2] = 1(5/5), 10(5+5), 0(5-5), 55, 25(5*5)
dp[3] = dp[1]+dp[2], dp[2]+dp[1] 의 경우
예를 들면, 5+1, 5/1, 5..... 또 5+10, 5/10 이런식으로 dp[i 가 되는 값들] 을 계산해서 중복 되지 않도록 HashSet을 사용하였고 값을 넣고 해당 number가 contain 되면 return 하는 식 풀었다.