[프로그래머스 Level 3] N으로 표현 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(N, number) {
    const dp = Array.from({ length: 9 }, () => new Set());
    dp[1].add(N);
    
    for (let i = 1; i <= 8; i++) {
        dp[i].add(Number(String(N).repeat(i)));
        for (let j = 1; j < i; j++) {
            for (const num1 of dp[j]) {
                for (const num2 of dp[i - j]) {
                    dp[i].add(num1 + num2);
                    dp[i].add(num1 * num2);
                    dp[i].add(num1 - num2);
                    dp[i].add(Math.floor(num1 / num2));
                }
            }
        }
        if (dp[i].has(number)) {
            return i;
        }
    }
    
    return -1;
}

dp 배열에 숫자 N을 사용한 횟수를 인덱스로 하여 배열의 값으로 최소 인덱스 만큼 N을 사용하여 표현할 수 있는 수들의 집합을 저장한다. 예를 들어, N을 최소 3번 사용하여 표현할 수 있는 수들은 모두 dp[3]의 집합에 저장하는 방식이다.

 

dp[1]은 N을 1회 사용한 값들이 들어가야 하는데 이는 N 하나로 유일하다.

dp[2]는 N을 1회 사용한 값, 즉 dp[1]의 값 중 두 개를 연산하여 만들 수 있다.

dp[3]은 dp[1]의 값 중 하나와 dp[2]의 값 중 하나를 연산하여 만들 수 있다.

dp[4]는 dp[1]의 값 중 하나와 dp[3]의 값 중 하나를 연산하거나, dp[2]의 값 중 두 개를 연산하여 만들 수 있다.

즉 dp[n]은 dp[1]의 값 중 하나와 dp[n - 1]의 값 중 하나를 연산하거나, .... , dp[n - 1]의 값 중 하나와 dp[1]의 값 중 하나를 연산하여 만들 수 있다.

 

예를 들어 N = 5이면,

dp[1] = Set { 5 }

 

dp[2]는 5 + 5, 5 - 5, 5 * 5, 5 / 5의 값들이 모두 가능하므로 dp[2] = Set { 0, 1, 10, 25 }이다. 

그런데 사실 55라는 수도 dp[2]에 속해야 한다. 5를 두개 이어 붙이는 경우도 가능하기 때문이다.

이런 경우를 생각해서 dp[n]을 계산할 때 항상 먼저 N이 n번 반복되는 수를 추가해줘야 한다.

따라서 dp[2] = Set { 0, 1, 10, 25, 55 }이다.

 

dp[3]은 dp[2]의 5개의 수끼리 사칙연산한 결과와 555를 포함한 집합이다.

dp[3] = Set { -50, -20, -5, -4, 0, 2, 4, 5, 6, 11, 15, 20, 30, 50, 60, 125, 275, 555, Infinity }

집합에 음수와 Infinity같은 값들이 들어가는 것은 사칙연산시 피연산자들의 범위를 제한하지 않아서이다. 피연산자의 범위를 음수와 무한대가 나오지 않도록 조정한 것과 조정하지 않은 것은 문제 풀이와 속도에 큰 차이가 없기 때문에 무시하겠다. 만약 이렇게 풀려면 아래와 같이 뺄셈과 나눗셈의 경우에 조건문을 추가하면 된다.

if (num1 > num2) {
  dp[i].add(num1 - num2);
}
if (num2 > 0) {
  dp[i].add(Math.floor(num1 / num2));
}

 

이렇게 dp[n]는 합이 n이 되는 i, j의 dp[i]의 값들과 dp[j]의 값들의 연산 결과를 모두 구하면 된다. 그리고 dp[n]에 대한 연산이 끝날 때마다 dp[n]의 집합에 number가 포함되어 있는지 확인 후, 존재한다면 그 즉시 n을 반환한다. dp[n + a] 에서 number가 나온다고 해도 구하고자 하는 값은 가장 작은 n이기 때문에 더 이상 탐색을 하지 않아도 된다. 문제의 조건에 따라 만약 모든 dp[8]까지 구했는데도 number가 포함되어 있는 dp[n]이 없다면 -1을 반환하면 된다.