문제 설명

아래와 같이 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 함수를 작성하세요.

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        int answer = 0;
        // 숫자 N과 number가 주어질 때, N과 사칙 연산만 사용해서 표현할 수 있는 방법 중 
        // N 사용횟수 최솟값.
        // N을 i번 사용해서 만들 수 있는 수의 집합 dp[i]
        // dp[i]에 number가 i를 리턴. i값이 8보다 크면 -1 리턴. i는 1~8.    
        List<Set<Integer>> dp = new ArrayList<>();
        // Set : 중복이 허용되지 않는 자료형.
        for (int i = 0; i <= 8 ; i++) { // 맵 초기화
            dp.add(new HashSet<>());
        }
        for (int i = 1; i <= 8; i++){
            //1. 이어붙인 숫자 추가.
            int num = 0;
            for(int k = 0; k < i ; k++){
                num = num*10 + N;
            }
            dp.get(i).add(num);
            
            // 이전에 있는 값에 연산 붙이기. 
            // ex) 11*11 dp[2]*[2]
            for(int j = 1; j < i ; j++) { // i= 4
                for(int o1 : dp.get(j)){
                    for(int o2 : dp.get(i-j)){
                        dp.get(i).add(o1+o2);
                        dp.get(i).add(o1-o2);
                        dp.get(i).add(o1*o2);
                        if(o2!=0){
                            dp.get(i).add(o1/o2);       
                        }
                    }
                }    
            }
            
            //System.out.println(dp);    
            
            if(dp.get(i).contains(number)){
                return i;
            }
            
        }
               
        return -1;
    } 
    
}

1. 핵심 개념

• 각 횟수 별 숫자 집합 dp[i]. i는 i번째 횟수의 숫자 전체 집합

• 숫자 집합의 구성은 1) N을 i번 이어붙인 숫자 + 2) 이전 집합들의 사칙 연산 후 숫자

첫 시도에서는 무조건 한 칸 이전 집합만 합쳤으나 그 경우 11*11 같은 케이스를 충족하기 어려움. 

            for(int j = 1; j < i ; j++) { // i= 4
                for(int o1 : dp.get(j)){
                    for(int o2 : dp.get(i-j)){
                        dp.get(i).add(o1+o2);
                        dp.get(i).add(o1-o2);
                        dp.get(i).add(o1*o2);
                        if(o2!=0){
                            dp.get(i).add(o1/o2);       
                        }
                    }
                }    
            }

해서 이전의 부분집합 항들을 전부 계산 해줘서 처리함.