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

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

코딩테스트 연습 > 동적계획법(Dynamic Programming) > N으로 표현

 

난이도: LEVEL3

알고리즘 유형: 완전 탐색?

풀이 설명

문제 카테고리는 동적계획법 dp 이지만 나는 완전 탐색으로 풀었다. 

어떻게 보면 이전 depth의 경우의 수를 기록하니 dp - 메모제이션 방식인 것 같기도 하다.

 

n을 1개 사용 ~ n을 8개 사용까지 모든 경우의 수를 다 구한다.

경우의 수 저장은 Set에 했다. 중복된 수가 있다. 

static ArrayList<Set<Integer>> list = new ArrayList<>();

index i의 의미: n을 i개 사용 

 

depth를 1씩 늘리면서 Set에 찾는 값이 있는지 확인한다. 

 

Set에 값을 넣는 방식 

ex)

n = 4

1, 3 / 2, 2 / 2, 2 / 3, 1 / 4 

더하기 곱하기는 순서와 상관없지만 나누기 빼기는 순서에 따라 달라진다. 

4의 의미는 순수하게 사칙연산 없이 n만 사용

1, 3 같은 경우는 n을 1개 사용과 n을 3개 사용의 사칙연산이다.

정답 코드 

import java.util.*;
class Solution {
    static ArrayList<Set<Integer>> list = new ArrayList<>();
    static int n; 
    static int target;
    static int answer = 9;
    public int solution(int N, int number) {
        n = N; 
        target = number;
        init();
        bt(1);
        return answer == 9 ? -1 : answer;
    }
    public static void bt(int depth){
        if(list.get(depth).contains(target)){
            answer = depth;
            return;
        }
        if(depth == 8) return;
        int next = depth + 1;
        Set<Integer> nextSet = list.get(next);
        for(int i = 1; i <= depth; i++){
            Set<Integer> set1 = list.get(i);
            Set<Integer> set2 = list.get(next - i);
            for(int cur1 : set1){
                for(int cur2: set2){
                    nextSet.add(cur1 + cur2);
                    nextSet.add(cur1 - cur2);
                    nextSet.add(cur1 * cur2);
                    if(cur2 == 0) continue;
                    nextSet.add(cur1 / cur2);
                }
            }
        }
        bt(next);
    }
    public static void init(){
        StringBuilder sb = new StringBuilder();
        list.add(new HashSet<>()); // 0 index 
        for(int i = 1; i <= 8; i++){
            sb.append(n);
            list.add(new HashSet<>());
            list.get(i).add(Integer.parseInt(sb.toString()));
        }
    }
}