[프로그래머스] N으로 표현 - Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

 

---

 

N을 i번 반복하여 만든 숫자를 먼저 dp[i]에 추가합니다. 예를 들어, N = 5이고 i = 3이라면 555라는 숫자를 추가

두 개의 작은 집합을 결합하여 새로운 숫자를 만들어냄. 예를 들어, dp[2]에서 55와 dp[1]에서 5를 이용해 dp[3]에서 555, 50, 275 등을 만든다

 

 

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        if (N == number) {
            return 1;
        }
        
        List<Set<Integer>> dp = new ArrayList<>();
        for (int i = 0; i <= 8; i++) {
            dp.add(new HashSet<>());
        }

        dp.get(1).add(N);

        for (int i = 2; i <= 8; i++) {
            int baseNum = Integer.parseInt(String.valueOf(N).repeat(i));
            dp.get(i).add(baseNum);

            for (int j = 1; j < i; j++) {
                for (int num1 : dp.get(j)) {
                    for (int num2 : dp.get(i - j)) {
                        dp.get(i).add(num1 + num2);
                        dp.get(i).add(num1 - num2);
                        dp.get(i).add(num1 * num2);
                        if (num2 != 0) {
                            dp.get(i).add(num1 / num2);
                        }
                    }
                }
            }
            
            if (dp.get(i).contains(number)) {
                return i;
            }
        }
        return -1;
    }
}