[프로그래머스] N으로 표현

 - DP 는 아직 할 때마다 감이 잘 안 온다

 - 기본 아이디어

   - TOP-BOTTOM && BOTTOM-TOP 방식을 기억을 잘 할 것 (이전 단계의 값을 저장해서 내려가거나 올라간다)

   - 한번에 다 하는 것이 아니라 쪼갠다 (recursive 한 부분인 것을 잘 기억)

   - 조건을 잘 찾을 수 있게 생각해야 한다.

 

 

  - 풀이는 답을 보고 했던 부분이지만 설명

    - 미리 1~8단계까지 SET 형태의 자료구조로 준비

    - i-> 1-> 8 까지 돌면서 N 횟수가 커지는 것을 표현

    - j

        -> 1단계일 경우 N

                                   -> N

 

        -> 2단계일 경우 NN

                                   -> NN

                                   -> N (+N, -N, *N, /N)

 

        -> 3단계일 경우 NNN

                                   -> NNN

                                   -> NN (+N, -N, *N, /N),

                                   -> N +N (+N, -N, *N, /N), N -N (+N, -N, *N, /N), N *N(+N, -N, *N, /N), N /N(+N, -N, *N, /N)

 

    이런 식으로 표현하면서 해당 값들을 단계에 계속 저장해 나간다.

    8단계를 넘는다면 -1

 

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        int answer = -1;
        Map<Integer, Set<Integer>> numMap = new HashMap();
        int nValue = N;
        for(int i = 1; i < 9; i++) {
            if(i > 1) {
                nValue += N*Math.pow(10, (i-1));   
            }
            Set<Integer> set = new HashSet();
            set.add(nValue);
            numMap.put( i, set);
            
        }
        int mapSize = numMap.size();
        for(int i=1;i<9;i++) {
            for(int j=1; j<i; j++) {
                for(Integer args1: numMap.get(j)) {
                    // System.out.println(args1);
                    // System.out.println(i-j);
                    for(Integer args2: numMap.get(i-j)) {
                        Set<Integer> set = numMap.get(i);
                        set.add(args1 + args2);
                        set.add(args1 - args2);
                        set.add(args1 * args2);
                        if(args2 != 0) {
                            set.add(args1 / args2 >> 0);
                        }
                    }
                }
            }
            if(numMap.get(i).contains(number)) {
                answer = i;
                break;
            }
        }
        return answer;
    }
}