[Programmers:DP] N으로 표현

❓문제

숫자 N을 8개 이하와 사칙연산만을 사용해서 number 만들 때 N 사용횟수의 최솟값 구하기(단, 8개 이상 사용하면 -1)

---

🖐️손코딩

• DP를 사용해서 dp[i] = N을 i개 사용해서 만들 수 있는 모든 숫자의 집합(Set) 
• EX) N = 5, number = 12 dp[1] = 5 dp[2] = 55 5+5 5-5 5*5 5/5 dp[3] = 555 55-5(dp[2] - dp[1]) 55+5(dp[2] + dp[1]) 55/5(dp[2] / dp[1]) 55*5(dp[2] * dp[1]) ... 이런식으로 dp[4]를 만들 수 있는 방법은 dp[1]+d[3] dp[2]+dp[2] dp[3]+dp[1] 의 조합 즉, for(i=현재) for(j=1부터 현재-1까지) for(k=현재-j) j+k j-k j*k j/k

---

👩‍💻구현 코드

import java.util.*;
//N과 사칙연산만 사용해서 number만들기

class Solution {
public int solution(int N, int number) {
int answer = -1;
Set[] dp = new HashSet[9];
int num = 0;

for(int i = 0; i<9; i++){
        dp[i] = new HashSet<Integer>();
    }

    for(int i = 1; i<=8; i++){
        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)){
            answer = i;
            break;
        }
    }

    return answer;
}

---

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