문제

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

문제 설명

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

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

---

Approach

풀고 나면 코드는 길지 않은데... 역시 DP.. ㅎㅎㅎㅎㅎㅎ

메모이제이션을 사용하는 정석 DP 문제였다.
숫자 N을 최소횟수로 사용해 주어진 number를 구하는 것이기 때문에,
N을 1번 사용 ->
N을 2번 사용 ->
N을 3번 사용 ->
...
N을 8번 사용 ->

N을 사용하는 횟수별로 숫자들을 순차적으로 구해줬다. (이 값을 저장해두고 다음 값 구할때 사용!)

이때 예를들어 N을 3번 사용하는 경우를 계산할때는, 앞서 구했던 N을 1번 사용하는 경우와 N을 2번 사용하는 경우를 더해주면 되기 때문에 이전에 구한 값을 사용해 현재 값을 구하는 전형적인 DP 로직이었다!

처음 풀고나서 정확도가 44.4%밖에 통과하지 못했었는데,
예를들어 N을 4번 사용하는 경우를 (1번사용+3번사용) 경우밖에 구하지 않아서였다.
하지만 -와 /연산의 경우 숫자의 위치가 바뀌면 연산 결과가 달라지기에 (3번+1번) 경우도 구해줘야 했고, 또 (2번+2번)의 경우도 있다.

결국 N을 4번 사용하는 경우는 (1번+3번), (2번+2번), (3번+1번) 모두 구해줘야 모든 경우의 수가 구해진다. (나머지 숫자들도 마찬가지)

dp배열을 만들어줬고, 그 배열 안에 i번째 인덱스에 새로운 배열을 만들어줬다. 해당 배열에는 N을 i번 사용했을때 구할수 있는 모든 숫자들이 들어가게 된다.

N=5일때 예시

[[], [5], [10,5,25,1,55], [...]]

i=0, 계산 편의를 위해 빈 배열 넣어줬다.

i=1, 5를 1번 사용했을때 구할수 있는 수이기 때문에 [5]

i=2, 5를 2번 사용했을때 구할수 있는 수들 
(1번사용했을때 숫자+1번사용했을때 숫자)
5+5 = 10
5-5 = 0
5*5 = 25 
5/5 = 1
55
총 5개의 숫자가 구해진다.

최솟값이 8보다 크면 -1을 리턴하라고 문제에서 주어졌기 때문에, while문의 조건을 count<=8로 설정해줬고,
dp배열에서 count번째 배열에 주어진 number가 존재하면 count를 리턴해줬다.

while문 안의 while문은 N을 count번 사용했을때 만들어질수 있는 숫자들을 구하기 위한 반복문인데,
예를들어 count가 5라면(N을 5번사용), 앞에서 구했던 count=1,2,3,4인 경우의 숫자들중 (1+4),(2+3),(3+2),(4+1)의 조합이 가능하게 된다.

이때 숫자 배열을 구할때 중복을 제거하기 위해서 set 자료구조를 사용했다!

Solution

function solution(N, number) {
    let num = N;
    let count = 1;
    let targetNum = number;
    
    // edge case
    if(num == targetNum) return 1;
    
    let dp = [[], [num]];
    while(count<=8){
        let targetArr = dp[count];
        if(targetArr.includes(targetNum)) return count;
        count++;
        
        let newNumSet = new Set();
        
        let i=1;
        while(i<count){
            for(let n1 of dp[i]){
                for(let n2 of dp[count-i]){
                    newNumSet.add(n1+n2); 
                    newNumSet.add(n1-n2);
                    newNumSet.add(n1*n2);
                    newNumSet.add(parseInt(n1/n2));
                }
            }
            i++;
        }
        newNumSet.add(Number(num.toString().repeat(count)));
        dp.push([...newNumSet]);
        //console.log([...targetArr])
    }
    return -1;
}

Solution 리팩토링

풀이를 정리하고 살펴보니 굳이 set을 다시 배열로 만들어줄 필요가 있을까? 싶기도 하고 ...
코드가 가독성이 좀 떨어지는 것 같아서 다시 리팩토링 해봤다.

function solution(N, number) {
    const dp = new Array(9).fill().map(()=> new Set());
    for(let i=1; i<9; i++){
        dp[i].add(Number(N.toString().repeat(i)));
        for(let j=1; j<i; j++){
            for(let n1 of dp[j]){
                for(let n2 of dp[i-j]){
                    dp[i].add(n1+n2); 
                    dp[i].add(n1-n2);
                    dp[i].add(n1*n2);
                    dp[i].add(parseInt(n1/n2));
                }
            }
        }
        if(dp[i].has(number)) return i;
    }
    return -1;
}