[백준] 모노디지털 표현 (2287, Java)

문제

몇 개의 숫자 K(K는 1, 2, …, 9중 하나)와 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)만을 사용하여 어떤 자연수 X를 수식으로 표현한 것을 X의 K-표현이라 부른다. 수식에는 괄호가 포함될 수 있으며, 나눗셈은 나눈 몫만을 취한다.

예를 들어 12의 5-표현을 몇 개 써 보면 5+5+(5/5)+(5/5), 55/5+5/5, (55+5)/5 등이 있다. K-표현의 길이를 사용한 K의 개수라 하면, 각각의 길이는 6, 5, 4가 된다.

K가 주어졌을 때, 어떤 자연수의 K-표현 중 가장 짧은 길이를 알아보려 한다.

입력

첫째 줄에 K가 주어진다. 다음 줄에는 표현 식을 찾을 수의 개수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 줄에는 K-표현 중 가장 짧은 길이를 알아보려 하는 자연수 a(1 ≤ a ≤ 32,000)가 주어진다.

출력

입력되는 순서대로 K-표현의 최소 길이를 n개의 줄에 출력한다. 만약 K-표현의 최소 길이가 8보다 크다면 “NO"를 출력한다.

예제 입력 1

5
2
12
31168

예제 출력 1 

4
NO

 

 

• k값과 이를 통해 만들어야 하는 값인 a를 가지고 8개 안으로 만들 수 있다면 그 수를 리턴하고 그렇지 않다면 NO를 출력해야 하는 문제이다.
• 생각해줄 수 있는 것은 수를 만들 때 사용할 수 있는 최대 개수가 8개이기 때문에 이를 집합(Set)의 배열로 만들어준 뒤 base value로부터 bottom-up 방식의 dp로 풀어나갈 수 있지 않을까 하는 것이다.
• 위에서 언급한 base value 값은 k, kk, kkk, kkkk.... 식의 값들이고 이는 k는 1번째 index, kk는 2번째 index의 집합(그 뒤는 생략)에 넣어주었다.
• 한 개로 만들 수 있는 값은 k 하나로 자명하기 때문에 이는 고려하지 않고 그 뒤에 2개부터 8개까지 루프를 돌면서 만일 값이 4일 때 (1st idx,3rd idx),(2nd idx,2nd idx),(3rd idx,1st idx)의 수 조합을 통하여 사칙연산을 해준 뒤 Set에 넣어주었다. (물론, 결과값이 기준치를 넘어가거나 그 밑으로 내려가는 경우는 제외하였다.)
• 마지막으로, n개의 a 값을 위에서 구한 set의 집합을 쭉 돌면서 존재하는 경우는 해당 index를 리턴하고 그렇지 않다면 NO를 리턴하는 식으로 문제를 풀이하였다.

 

import java.util.*;
import java.io.*;

public class Main {

    static int k, n;
    static boolean checked[];
    static Set<Integer>[] group;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        k = stoi(br.readLine());
        n = stoi(br.readLine());
        group = new Set[9];
        checked = new boolean[1000000];

        for (int i = 1; i <= 8; ++i) {
            group[i] = new HashSet<>();
        }
        int num = k;
        for (int i = 1; i <= 6; ++i) {
            checked[num] = true;
            group[i].add(num);
            num *= 10;
            num += k;
        }

        for (int i = 2; i <= 8; ++i) {
            for (int j = 1; j < i; ++j) {
                for (int x : group[j]) {
                    for (int y : group[i-j]) {
                        if (x + y < 1000000 && !checked[x+y]) {
                            checked[x+y] = true;
                            group[i].add(x+y);
                        }
                        if (y != 0 && x / y > 0 && !checked[x/y]) {
                            checked[x/y] = true;
                            group[i].add(x/y);
                        }
                        if (x - y >= 0 && !checked[x-y]) {
                            checked[x-y] = true;
                            group[i].add(x-y);
                        }
                        if (x * y < 1000000 && !checked[x*y]) {
                            checked[x*y] = true;
                            group[i].add(x*y);
                        }
                    }
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            int a = stoi(br.readLine());
            if (!checked[a]) {
                sb.append("NO\n");
                continue;
            }
            for (int k = 1; k <= 8; ++k) {
                if (group[k].contains(a)) {
                    sb.append(k + "\n");
                    break;
                }
            }
        }
        System.out.print(sb);
        br.close();
    }

    static int stoi(String input) {
        return Integer.parseInt(input);
    }


}