[프로그래머스] Lv.3 N으로 표현 JavaScript

문제 설명

아래와 같이 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번만 사용하여 표현할 수 있습니다.

---

문제풀이

이 문제는 동적 프로그래밍(Dynamic Programming, DP)과 관련된 문제로, 주어진 숫자 N과 일련의 연산을 사용하여 특정 숫자 number를 만들 수 있는 최소 연산 횟수를 구하는 문제이다.

1. dp 배열 초기화: dp는 길이 9의 배열로, 각 인덱스에 해당 숫자를 만들 수 있는 모든 조합을 저장하는 집합(Set)이다.

2. N을 한 번 사용하여 각 자릿수의 숫자를 생성하고 집합에 추가한다. 예를 들어, N이 5인 경우 dp[1]에는 5를, dp[2]에는 55(5를 2번 연이어 사용한 숫자)를 추가한다.

3. i와 j 이중 반복문: 이중 반복문을 사용하여 dp[i]와 dp[j]를 조합하여 dp[i]를 만든다.

   • i는 탐색하려는 숫자 길이(1부터 8까지)이다.
   • j는 현재 숫자 길이보다 작은 숫자 길이(1부터 i-1까지)이다.

4. a와 b를 이용한 연산: dp[j]에 있는 숫자 a와 dp[i-j]에 있는 숫자 b를 이용하여 가능한 모든 연산을 수행하고 그 결과를 dp[i]에 추가한다. 가능한 연산은 덧셈, 뺄셈, 곱셈, 나눗셈(정수 나눗셈)이다.

   dp[j]에 있는 숫자 a와 dp[i - j]에 있는b는 현재 사용한 N의 횟수에 따라 나올 수 있는 모든 숫자 조합을 나타낸다.

   예를 들어, dp[1]에는 N을 1번 사용한 경우의 수가 저장되어 있다. 따라서 dp[1]은 [N]을 저장한다.

   dp[2]의 경우, N을 2번 사용한 경우의 수를 저장해야 합니다. 여기서 dp[1]에 있는 숫자 a와 b를 조합하여 dp[2]에 저장한다. 이때 가능한 조합은 다음과 같다:

   • N을 2번 사용하는 경우: [N + N, N - N, N * N, N / N]를 dp[2]에 추가한다.
   • N을 3번 사용하는 경우: N을 1번 사용하는 경우와 N을 2번 사용하는 경우를 사칙연산하여 저장한다.
   • N을 4번 사용하는 경우: N을 (1번 3번), (2번 2번), (3번 1번) 사용하는 경우를 사칙연산하여 저장한다.

   이러한 방식으로, dp[j]에 있는 숫자 a와 dp[i - j]에 있는 숫자 b는 각각 N을 j번과 (i - j)번 사용한 경우의 수를 나타내며, 두 조합을 모두 고려하여 dp[i]에 저장된다. 이를 반복하면서 모든 가능한 N 사용 횟수에 대한 숫자 조합을 계산한다.

5. number가 dp[i]에 있으면 반환: 각 단계에서 dp[i]를 만들 때마다 number가 포함되어 있는지 확인하고, 있다면 i를 반환한다.

6. 만약 number를 만들 수 없다면 -1을 반환한다.

이렇게 하면 dp[i]에는 N을 i번 연속 사용하여 만들 수 있는 숫자들이 저장되고, number가 나타나는 순간 그 때의 i를 반환하여 최소 연산 횟수를 찾아낸다.

✅ 답안

function solution(N, number) {
    let dp = new Array(9).fill(0).map(() => new Set()); // DP 테이블 초기화
    for (let i = 1; i < 9; i++) {
		// 숫자 N을 i번 반복한 수 생성
        const num = Number(N.toString().repeat(i));
        dp[i].add(num); // DP 테이블에 추가
    }
    for (let i = 1; i < 9; i++) {
        for (let j = 1; j < i; j++) {
            for (const a of dp[j]) {
                for (const b of dp[i - j]) {
                    dp[i].add(a + b);
                    dp[i].add(a - b);
                    dp[i].add(a * b);
                    dp[i].add(Math.floor(a / b));
                }
            }
        }
        if (dp[i].has(number)) return i;
    }
    return -1; // 답을 찾지 못한 경우
}