Programmers N으로 표현 java 풀이

문제 설명

아래와 같이 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 합니다.

나의 풀이

 이번 문제는 어려웠다.. 먼저 다이나믹 프로그래밍(DP) 개념에 대한공부가 선행되면 좋고, 이 문제는 효율성 테스트가 없고 최대 숫자의 갯수가 8개이기 때문에 DP가 아니라 전체를 스캔하며 답을 찾는 DFS, BFS 등의 방식으로도 풀 수는 있다. 하지만 문제 자체가 DP 분류에 있기 때문에 가능하면 DP로 풀어보고자 했는데... DP에 대한 개념은 이해를 했지만 문제풀이는 사실 실패해서 다른사람들의 풀이를 최대한 많이 찾아보고 디버깅해보면 풀었다. 어려웠던 점은 DP에 대한 개념보다는 주어진 숫자 N과 최소한의 횟수로 찾아야하는 수 number간의 식을 찾는게 어려웠다.

 

 이해한 바를 간단히 정리하자면

 숫자 N(5라고 가정)을 사용해서 만들 수 있는 수는

 

 N을 1번 사용했을땐 

    5

 

 N을 2번 사용했을땐

    55(N을 연속 2번)

    5(N을 1번 사용해서 만든수) *N

    5(N을 1번 사용해서 만든수) /N (단 나누는 수가 0이 아니여야한다.)

    5(N을 1번 사용해서 만든수) +N

    5(N을 1번 사용해서 만든수) -N

 

N을 3번 사용했을땐

   555(N을 3번 반복)

   5를 2번사용해서 만든수를 5로 사칙연산

 

이와같은 패턴이 반복되기 때문에 이를 반복 수행하되, DP인 만큼 외부에 Set으로 이뤄진 배열을 선언하고 저장하면서 실행하였다

 

 

 

코드

import java.util.*;

class Solution {
    static int tempN;
    TreeSet<Integer>[] arr;
    
    public TreeSet<Integer> getNum(int n) {
        if((arr[n]!=null) && !arr[n].isEmpty())
            return arr[n];
        
        int num = 0;
        for(int i=0; i<n ; i++)
            num = 10*num + tempN;
        
        TreeSet<Integer> temp = new TreeSet<>();
        temp.add(num);
        
        for(int i=1; i<n; i++) {
            int j = n-i;
            TreeSet<Integer> from = getNum(i);
            TreeSet<Integer> to = getNum(j);
            for(int n1 : from) {
                for(int n2 : to) {
                    temp.add(n1+n2);
                    temp.add(n1-n2);
                    temp.add(n1*n2);
                    if(n2!=0) temp.add(n1/n2);
                }
            }
        }
        return arr[n] = temp;
    }
    public int solution(int N, int number) {
        int answer = 0;
        tempN = N;
        arr = new TreeSet[10];
        for(int i=1; i<=8; i++) {
            getNum(i);
            if(arr[i].contains(number)) 
                return i;
        }
        
        return -1;
    }
}