🔍 Problem

N으로 표현

---

📃 Input&Output

---

🌁 문제 배경

가. 문제 설명
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

1) 12 = 5 + 5 + (5 / 5) + (5 / 5)
2) 12 = 55 / 5 + 5 / 5
3) 12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

[요약]
12 = 5 + 5 + (5 / 5) + (5 / 5)와 같이 주어진 N(5)으로 number(12)를 만들 때, 최소로 사용할 수 있는 N(5)의 개수를 return하는 문제이다. 참고로 최소로 사용할 수 있는 N의 개수는 8이 최대이다. 9이상 넘어가면 -1을 Return한다.

나. 접근 방법
N의 개수를 1부터 8까지 증가하여 number값이 나왔을 때, 당시 사용한 N의 개수를 return한다. 각 개수별로 나올 수 있는 모든 값을 구하는 방식이다.

[구하는 방식]
만약 사용된 N의 개수가 3이라면?

1) 1개의 N을 사용해서 나온 값들 (사칙연산) 2개의 N을 사용해서 나온 값들
2) 2개의 N을 사용해서 나온 값들 (사칙연산) 1개의 N을 사용해서 나온 값들
3) 3개의 N

위의 경우들이다. 필자가 왜 1번 상황과 2번 상황을 하나로 보지 않았냐면 사칙연산의 특성상, -, % 같은 경우 앞뒤 순서에 따라 결과가 달라지기 때문이다.

다. 문제 유형
DP

---

📒 수도 코드

가. number와 N이 같으면 1을 출력

나. HashSet으로 구성된 List 생성 및 초기화
HashSet을 사용하는 이유는 중복을 제거하기 위해서이다.

다. 2부터 8까지 순회하여 각 Set에 들어갈 값들 초기화
2부터 8인 이유는 N을 1번 사용(1인 경우)해봤자 결국 N하나 밖이 없기 때문이다.
ex. N=2, N을 1번 사용한 경우 : 2 (끝)

라. for문 돌려서 사칙연산 및 N을 n번 사용한 경우의 n번 반복 구현
아래는 N을 i번 사용한 경우의 HashSet과 i개의 N을 구하는 수도코드

for ( i =1~8)
	List[i].add([N을 1번 사용한 경우 HashSet의 값들] (사칙연산) [N을 i-1번 사용한 경우의 HashSet의 값들])
    
List[i].add(N*i번)

---

💻 Code

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        if (number == N) return 1;
        
        List<HashSet<Integer>> list= new ArrayList<>();
        
        for (int i=0; i<9; i++){
            list.add(new HashSet<Integer>());
        }
        
        list.get(1).add(N);
        
        for (int n=2; n<=8; n++){
            for (int i=1;i<n;i++){
                int j=n-i;
                
                for(int a : list.get(i)){
                    for(int b : list.get(j)){
                        list.get(n).add(a+b);
                        list.get(n).add(a-b);
                        list.get(n).add(a*b);
                        if(a!=0 && b!=0){
                            list.get(n).add(a/b);
                        }
                    }
                }
            }
            list.get(n).add(Integer.parseInt(String.valueOf(N).repeat(n)));
            
            if(list.get(n).contains(number)){
                return n;
            }
        }
        
        
        
        return -1;
    }
}

---

🎸 기타

가. String.repeat(n)
문자열을 n번 반복

나. HashSet.contains(value)
해당 value값을 가지고 있으면 true return

---

🤔 느낀점

DP를 떠올리기 쉽지 않았고 구현 로직 자체가 최소값을 구하는게 아니라 사용횟수 자체를 구하는, 값이 먼저 나오면 그 값을 최소값으로 정하는 아이디어 자체를 떠올리기가 쉽지 않은 문제였다.