[알고리즘] 백준 > #2287. 모노디지털 표현

문제링크

백준 #2287. 모노디지털 표현

풀이방법

처음에는 BFS인가 싶었다. 근데 그렇게 풀자니 괄호처리가 곤란했다; 그래서 생각난게 DP였다. 식을 그대로 갖고있는 게 아니라 계산된 값과 값 사이의 사칙연산을 진행하는거다. 예를 들어서, 길이가 5인 5-연산을 진행한다면, 5 = 1 + 4 = 2 + 3임을 이용해 길이가 1인 5-연산과 길이가 4인 5-연산을 사칙연산으로 계산을 하는거다. 이렇게 하면 사실 5 + (5 + 5 + 5 + 5)인걸 계산하는 건데 이 식을 알 필요 없다. 그냥 그 결과만 갖고 계산을 진행하면 된다(5 + 20), (5 - 20) ... 근데 여기서 주의할 거는 (5 - 20) != (20 - 5)이다. 그래서 나는 총 6개 연산을 진행했다(나눗셈도 동일하다). 길이가 8로 한정되어있기 때문에 시간초과 없이 문제를 해결할 수 있었다. 그리고 dp는 Set의 배열로 구현했다. 겹치는 값이 생기면 불필요한 연산만 늘기 때문에 Set 자료구조를 이용했다.

코드

class Solution2287 {

    int k, n;
    int[] a;

    HashSet<Integer>[] dp;

    Solution2287(int k, int n, int[] a) {
        this.k = k;
        this.n = n;
        this.a = a;

        initDP();
    }

    String getResult() {
        StringBuilder results = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int result = 0;
            for (int time = 1; time <= 8; time++) {
                if (dp[time].contains(a[i])) {
                    result = time;
                    break;
                }
            }

            if (result == 0) results.append("NO");
            else results.append(result);
            results.append("\n");
        }

        return results.toString();
    }

    private void initDP() {
        dp = new HashSet[8 + 1];
        for (int i = 0; i < 8 + 1; i++) dp[i] = new HashSet<>();

        dp[0].add(0);
        int initVal = k;
        for (int i = 1; i <= 8; i++) {
            dp[i].add(initVal);

            initVal = initVal * 10 + k;
        }

        for (int i = 1;i <= 8; i++) {
            for (int j = 0; j <= i / 2; j++) {
                int diff = i - j;

                for (Integer valueDiff : dp[diff]) {
                    for (Integer valueJ : dp[j]) {
                        dp[i].add(valueDiff + valueJ);
                        dp[i].add(valueDiff - valueJ);
                        dp[i].add(valueJ - valueDiff);
                        dp[i].add(valueDiff * valueJ);
                        if ((valueJ != 0)) dp[i].add(valueDiff / valueJ);
                        if ((valueDiff != 0)) dp[i].add(valueJ / valueDiff);
                    }
                }
            }
        }
    }
}