프로그래머스 - N으로 표현

숫자 N을 2번 사용한 경우의 결과는 1번 사용한 경우와 1번 사용한 경우의 사칙연산 + NN식으로 붙인 경우가 있다.

숫자 N을 3번 사용한 경우의 결과는 NNN으로 합친 것 하나 + 숫자를 [2, 1]번 사용한 경우와 [1,2]번 사용한 경우를 사칙연산으로 합친 결과와 같다.

숫자 N을 4번 사용한 경우의 결과는 NNNN으로 합친 것 하나 + 숫자를 [3, 1], [2, 2], [1, 3]번 사용한 경우의 사칙연산의 결과와 같다.

즉, 큰 문제를 작은 문제 결과를 합쳐서 계산할 수 있으므로, 동적 계획법으로 답을 구할 수 있다. 이때, bottom-up 방식으로 결과를 작은 것부터 계산하여, 목표로 하는 값이 존재하는 경우에 계산을 멈추고 결과를 반환한다.

여기서, 계산 결과가 0인 경우는 제외한다. 최솟값을 구하는 문제이므로, 계산할 필요가 없다.
음수인 경우는 잘 모르므로, 일단 추가한다.(이 문제의 테스트 케이스의 경우는 음수를 제외해도 정답처리는 됐다.)

교환법칙이 성립하는 덧셈과 곱셈을 제외한 다른 연산자를 추가하여 계산한다. 그래서 4번 사용한 경우를 예로 들면 [3, 1]과 [1, 3]을 추가로 계산하지 않도록 한다.

import java.util.*;
import java.util.function.LongBinaryOperator;

class Solution {
    public int solution(int N, int number) {
        if (N == number) {
            return 1;
        }
        
        List<Set<Long>> table = new ArrayList<>();
        table.add(null);
        Set<Long> first = new HashSet<>();
        first.add(Integer.valueOf(N).longValue());
        table.add(first);
        int answer = 2;
        Long constant = N * 10L + N;

        while (answer <= 8) {
            Set<Long> numbers = new HashSet<>();
            numbers.add(constant);
            
            if (constant == number) {
                return answer;
            }
            
            for (int i = answer - 1; i > 0; i--) {
                int j = answer - i;
                if (i < j) {
                    break;
                }
                
                for (Long iNumber : table.get(i)) {
                    for (Long jNumber : table.get(j)) {
                        for (Operator o : Operator.values()) {
                            Long result = o.apply(iNumber, jNumber);
                            if (result == number) {
                                return answer;
                            }
                            if (result != 0) {
                                numbers.add(result);
                            }
                        }
                    }
                }
            }
            
            table.add(numbers);
            answer++;
            constant = constant * 10 + N;
        }
        
        return -1;
    }
    
    static enum Operator {
        PLUS    ((a, b) -> a+b),
        MINUS   ((a, b) -> a-b),
        REVERSE_MINUS((a, b) -> b - a),
        MULTIPLY((a, b) -> a*b),
        DIVIDE  ((a, b) -> a/b),
        REVERSE_DIVIDE  ((a, b) -> b/a);
        
        private LongBinaryOperator op;
        
        Operator(LongBinaryOperator op) {
            this.op = op;
        }
        
        public long apply(long a, long b) {
            return op.applyAsLong(a, b);
        }
    }
}