[Programmers Lv.3] N으로 표현

🔗 Link

문제
풀이

📝 Problem Summary

💡 Idea

처음에는 다익스트라로 +N, -N, *N, /N 으로 갈 수 있는 곳을 탐색하면 되나 싶었는데, (N*N)+(N*N) 이런 경우도 표현해야 해서 안되겠다 싶음. 결국 내가 횟수가 1~i번으로 만들 수 있는 숫자들을 전부 계산시켜봐서, i+1번 계산으로 만들 수 있는 숫자들을 계산해야 함. 중복되는 숫자들을 처리하기 위해 Set으로 배열을 만들어줌.

• s[i] : i개 써서 만들 수 있는 숫자들

  🔑 Code

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        Set<Integer>[] s = new HashSet[9];
        for(int i = 1; i <= 8; i++){
            s[i] = new HashSet<>();
        }
        
        // 초기값 설정
        s[1].add(N);
        s[2].add(N+N);
        s[2].add(N*N);
        s[2].add(N/N);
        s[2].add(N*11);
        
        // 초기 탈출
        if(N == number) return 1;
        if(s[2].contains(number)) return 2;
        
        int one = 11;
        for(int i = 3; i <= 8; i++){
            one = one*10+1;
            s[i].add(N*one);
            
            for(int j = 1; j <= i/2; j++){
                // s[j]와 s[i-j]에 있는 원소들로 사칙연산
                for(int a : s[j]){
                    for(int b : s[i-j]){
                        int[] result = {a+b, Math.abs(a-b), a*b, (a>=b) ? a/b : b/a};
                        for(int r: result){
                            if(r <= 0) continue;
                            boolean isExisted = false;
                            for(int k = 1; k < i; k++){
                                if(s[k].contains(r)){
                                    isExisted = true;
                                    break;
                                }
                            }
                            if(!isExisted) s[i].add(r);
                        }
                        
                    }
                }
            }
            if(s[i].contains(number)) return i;
        }
        
        return -1;
    }
}

🗨️ Side Notes