Solution.java

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        int answer = -1;
        
        HashSet<Integer>[] dp = new HashSet[8];
        
        int tmp = 0;
        for (int i = 0; i < 8; i++) {
            tmp = tmp * 10 + N;
            dp[i] = new HashSet<>();
            dp[i].add(tmp);
        }
        
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < Math.min(7 - i, i + 1); j++) {
                for (int num1 : dp[i]) {
                    for (int num2 : dp[j]) {
                        dp[i + j + 1].add(num1 + num2);
                        if (num1 != num2) dp[i + j + 1].add(Math.abs(num1 - num2));
                        dp[i + j + 1].add(num1 * num2);
                        dp[i + j + 1].add((num1 >= num2) ? num1 / num2 : num2 / num1);
                    }
                }
            }
        }
        
        for (int i = 0; i < 8; i++) {
            if (dp[i].contains(number)) {
                answer = i + 1;
                break;
            }
        }
        
        return answer;
    }
}

DP를 이런식으로도 쓸 수 있구나 배웠던 문제였다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges