[Dynamic Programming] Programmers 코딩테스트 연습 - N으로 표현 JAVA

N으로 표현

문제 설명
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

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

입출력 예

N number return
5 12 4
2 11 3

해설

이 문제를 JAVA를 이용한 DP로 풀이한 해설은 없는 것 같아서 여기에 남겨둔다.

목적 : 숫자 N을 최소 갯수로 활용하여 사칙 연산을 수행하여 number를 만들 수 있다면, 사용한 N의 최소 갯수를 return한다.

일단 정답 코드를 먼저 공개하겠다.

public class Solution {
    static int _N;
    TreeSet<Integer>[] dynamic;

    public TreeSet<Integer> solve(int n) {
        if ((dynamic[n]!=null) &&!dynamic[n].isEmpty()) return dynamic[n];//전에 있던 집합 찾기.
        int num = 0;
        for (int i = 0; i < n; i++) num = 10 * num + _N; // NNNN만들기.
        TreeSet<Integer> temp = new TreeSet<>();
        temp.add(num);
        for(int i =1; i<n;i++){
            int j = n-i;
            TreeSet<Integer> from = solve(i);
            TreeSet<Integer> to = solve(j);
            for(int n1:from) {
                for (int n2 : to) {//d[n] = d[n-1] + d[i];
                    temp.add(n1 + n2);
                    temp.add(n1 - n2);
                    temp.add(n1 * n2);
                    if(n2 != 0) temp.add(n1 / n2);
                }
            }
        }
        return dynamic[n]= temp;
    }


    public int solution(int N, int number) {
        int answer = 0;
        _N = N;

        dynamic = new TreeSet[10];
        for(int i =1 ; i<= 8; i++){
            solve(i);
            if (dynamic[i].contains(number)) return i;
        }
        return -1;
    }
}

로직을 간단히 설명하자.

1. dynamic 배열은 d[n] = d[n-i] + d[i]의 결과를 저장하기 위한 set 배열이다. 결과만 중요하고, 중복은 상관없다.
2. solve의 3번째 줄을 보면, n의 숫자 만큼 N을 이어붙인 int형 num을 계산한다. ex) n이 2이면 NN N이 0이면 0
3. 6번째 부터 보면, j는 n-i을 계산한다. 이는 i +j = n을 의미하는 것으로 N을 i번 사용해서 나온 연산의 결과는
4. dynamic[i]에 저장되어 있음을 의미한다.

   dynamic[j] = dynamic[n-i]는 만약 n이 6이고 i가 2였다면, dynamic[i]는 NN을 의미(N을 2번 사용하여 나온 결과)
   dynamic[N-i]는 NNNN의미 (N을 4번 사용하여 나온 결과 의미)
   만약 NNNN의 결과를 구한다면, N + NNN / NN + NN / N + NNN 이 세 가지를 통해 구하는 것을 의미한다.
   i는 즉 N을 몇번 활용했는가를 의미한다.
   또한, dp는 결과를 저장하는 집합의 배열이고, dp내부의 temp는 집합이 저장됨을 헷갈리면 안된다.

5. 만약 집합이 이미 계산 결과를 갖고 있는 temp 배열이라면 바로 dynamic의 결과 배열을 반환한다.
6. i는 i번만으로 number를 만들 수 있나? 를 의미하는 것이다. 그리고 그 안에는 지금까지 연산의 결과가 저장되어 있다.
7. 마지막으로 solution에서는 for loop를 통해 N을 i번 활용해서 나온 결과 중에 number가 있는지를 확인한다.

   treeset을 10으로 잡는 이유는 N을 최대 9번 곱해봤자 NNNNNNNNN이하의 결과만 나오기 때문이다.
   0도 맨 처음에 initialize시 dynamic[0] = {0}의 결과 집합이 되기 때문에 포함해 주어야 한다. i가 8 이상이면 -1을 리턴한다.

참조 : [https://programmers.co.kr/learn/courses/30/lessons/42895](프로그래머스 42895번 N으로 표현)