문제 접근

문제에서 N을 8 보다 많이 조합하지 말라고 나와있다.
즉, 생각보다 한계가 적은 문제다.

N이 1개인 경우 -> N
N이 2개인 경우 -> NN, N+N, N-N, NxN, N/N
N이 3개인 경우 -> NNN, NN+N, NN-N, N-NN, NNxN, NN/N, N/NN
...

이런 식으로 생각해보자. 잘 보자. N이 3개인 경우 N이 2개로 만들 수 있는 수들과 N을 1개로 만들 수 있는 수들의 조합이다.
즉, N을 2개로 만들 수 있는 수들의 결과를 미리 구해놨다면, 우리는 이걸 다시 연산하지 않아도 N을 3개로 만들 수 있는 수들을 구하는데 활용할 수 있다.

문제 풀이

import java.util.*;

class Solution {
    Set<Integer>[] dp = new HashSet[9];
    public int solution(int N, int number) {
        int answer = -1;
        for(int i=0; i<=8; i++) dp[i] = new HashSet();
        dp[1].add(N);
        
        if (N==number) return 1;
        
        int nnn = N;
        for(int i=2; i<=8; i++) {
            nnn*=10;
            nnn+=N;
            if (nnn==number) return i;
            dp[i].add(nnn);

            for(int a=1; a<=i-1; a++) {
                int b = i-a;
                for(int p: dp[a]) {
                    for(int q:dp[b]) {
                        int pq = p+q;
                        if (pq == number) return i;
                        dp[i].add(pq);

                        pq = p*q;
                        if (pq == number) return i;
                        dp[i].add(pq);
                        
                        if (q!=0) {
                            pq = p/q;
                            if (pq == number) return i;
                            dp[i].add(pq);
                        }
                        
                        if (p!=0) {
                            pq = q/p;
                            if (pq == number) return i;
                            dp[i].add(pq);
                        }
                        
                        pq = p-q;
                        if (pq == number) return i;
                        dp[i].add(pq);
                        
                        pq = q-p;
                        if (pq == number) return i;
                        dp[i].add(pq);
                    }
                }
            }
        }
        
        return answer;
    }
}

새롭게 알게 된 것

Set<제네릭>[] 변수 = new HashSet[갯수];
이렇게 만들어야 한다.
만약, Set<제네릭>[] 변수 = new HashSet<제네릭>[갯수];
여기에도 넣으려고 하면 에러가 난다. 주의하자.