[프로그래머스][LEVEL3]N으로 표현

# 문제 원문

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

코딩테스트 연습 - N으로 표현

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

출처

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

 

# 문제 풀이

 

프로그래머스 동적 계획법(Dynamic Programming)의 가장 기초적인 문제이다. DP(작은 부분의 반복)라는 구조는 프로그래밍 특징상 그리 특별한 것은 아니지만 알고리즘 상으로 보았을때는 유의미하게 DP라고 분류 할 수 있는 첫 문제인것 같다. 개인적으로 해당 문제는 직접적으로 0부터 풀기보다 DP에 관련해서 소소하게 공부하면서 팁을 얻었다. 기존 작업 단위의 결과들의 합이 다음 작업단위의 합이 된다는 간단한 로직이지만 DP라는 것을 어떻게 짜는지를 잘모른다면 어려울 문제이다. 지문에서 요구하는 N으로 number를 구성할 수 있는 수의 제한은 8이므로 8까지만 고려해주면 된다.

number가 나올때까지 기존 작업 단위를 순회하면서 가감승제를 해당 작업 단위의 합에 맞춰서 경우의 수들을 계속 더해주면 된다. 그러다 보니 자연히 N에서 N보다 작은 작업단위의 가장 높은 작업단위 + 가장 낮은 작업단위로 매칭 되는 규칙이 있는데 (총 작업단위 합이 N을 넘을 수 없기 때문이다.) 이해하기만 하면 그렇게 어려운 문제는 아니다.

 

# 솔루션 플로우

1. 입력 받은 N과 number가 같을 경우 바로 작업이 끝나니 1을 얼리 리턴한다.

2. N은 최대 8개 까지 사용 가능하므로 각 갯수를 사용한 경우의 수를 저장한 1차원 배열 dp를 만들어준다.

3. 만들어진 dp배열의 각 자릿수에 맞는 N을 이어붙인 경우의 수를 더해준다.

4. dp를 순회하면서 N을 최대 8개 까지 사용했을때 가능한 경우의 수들을 모두 찾는다.

5. dp의 idx는 N를 몇개까지 사용 했는지이므로 N - 1부터 0까지 0부터 N - 1까지 left, right의 합(가감승제)4가지를 구해준다.

7. dp 순회가 끝난후 number가 구해진다면 N을 가장 적게 사용한 값을 구하고 구해지지 않는다면 -1를 구한다.

8. 구해진 result를 반환한다.

1. FP

function solution(N, number) {
    if (N === number) return 1;
    const dp = Array.from(
        { length: 9 },
        (_, idx) => new Set([
            parseInt('1'.repeat(idx)) * N
        ])
    );

    return dp.reduce((result, current, idx) => {
        for (let count = 0; count < idx; count++) {
            for (const left of dp[count]) {
                for (const right of dp[idx - count]) {
                    if (right === 0) continue;
                    current.add(left + right);
                    current.add(left - right);
                    current.add(left * right);
                    current.add(left / right);
                }
            }
        }

        return result === -1 && current.has(number) ?
            idx :
            result;
    }, -1);
}