[프로그래머스](동적계획법) N으로 표현

N으로 표현 규칙

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하는 것이다.

1. N은 1 이상 9 이하입니다.
2. number는 1 이상 32,000 이하입니다.
3. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
4. 최솟값이 8보다 크면 -1을 return 합니다.

풀이
방법 : 주어진 N을 1개 사용하여 만들수 있는 숫자, N을 2개 사용하여 만들수 있는숫자, 3개 사용하여 만들수 있는 숫자...가 무엇인지를 계속해서 저장하면서 N을 몇개 사용할때 number숫자가 나오가를 찾으면된다.
최솟값이 8보다 크면 -1이기때문에, N을 8까지만 구하면된다고 생각하면됨

1. N이 5일경우, 사칙연산을 제외한 1개에서 5, 2개에서 55, 3개에 555 ...를 미리 넣어둔다.
2. int가 들어가는 Set을 8개 만들어 놓고, N이 1개, 2개, 3개..8개를 사용하여 만들 수 있는 숫자를 각 Set에 넣으면서 계산
3. N이 1개일때 Set : 5
   N이 2개일때 Set : 55와 1개 Set과 1개 Set을 사용하여 사칙연산
   N이 3개일때 Set : 555와 1개Set 과 2개 Set을 사용한 사칙연산과 2개Set과 1개Set을 사용한 사칙연산
   N이 4개일때 Set : 5555과 1개Set과 3개 Set을 사용한 사칙연산, 2개 Set과 2개Set을 사용한 사칙연산, 3개 Set과 1개 Set을 사용한 사칙연산
   ....

이렇게 계산해가면서 number가 나오는 N의 갯수를 찾으면된다.

package test;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class test12 {

    public static int getValue(int n, int count) {
        int ret = 0;

        while (count != 0) {
            count -= 1;
            ret += n * (int) Math.pow(10, count);
        }
        return ret;

    }

    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("src/test12.txt"))));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        // 9개 이상 사용하면 -1로 출력
        int max = 9;

        // N을 이용하여 1개사용시 숫자, 2개 사용시 숫자, 3개 사용시 숫자를 저장하기 위함
        HashSet<Integer>[] hs = new HashSet[max];

        // N을 이용하여 1개 일때, N, 2개일때, NN, 3개 일때, NNN 숫자를 만들어서 넣는다.
        for (int i = 0; i < max; i++) {
            hs[i] = new HashSet<Integer>();
            hs[i].add(getValue(n, i));
        }

        // 9개 이상 사용하면 -1로 출력
        int answer = -1;

        // N을 1개사용 할때 ~ 9개 사용할때 까지 loop
        for (int i = 1; i < max; i++) {
            // System.out.println("i counter " + i);

            // i = 1 : 5
            // i = 2 : 55, 1번으로 사칙연산
            // i = 3 : 555, 1번과 2번으로 사진연산, 2번과 1번으로 사칙연산
            // i = 4 : 5555, 1번과3번으로 사칙연산, 2번과 2번으로 사칙연산, 3번과 1번으로 사칙연산
            // ....
            for (int j = 1; j < i; j++) {
                for (int k : hs[j]) {
                    for (int t : hs[i - j]) {
                        hs[i].add(k + t);
                        hs[i].add(k * t);
                        hs[i].add(k - t);

                        if (t != 0) {
                            hs[i].add(k / t);
                        }
                    }
                }
            }

            if (hs[i].contains(x)) {
                answer = i;
                break;
            }
        }

        System.out.println(answer);
    }
}