[JS/알고리즘] DP : 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 합니다.

입출력 예Nnumberreturn

5	12	4
2	11	3

입출력 예 설명

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

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

 

 

문제 해결 방법

우선, DP라는 것에 주목해보자. DP의 대표적인 예제로 피보나치 수열이 있는데, 피보나치 수열의 다음 값 연산에서

이전 값들을 사용하는 것 처럼 다음 연산을 할 때, 이전 연산 들의 결과 값을 참조하는 방식이 DP이다.

쉽게 말해, 어떤 연산의 10번째 값을 구하기 위해서는 8번째와 9번째의 결과 값이 필요한 방식이다.

해당 문제도 이러한 논리로 접근하면 간단하게 해결할 수 있다.

5가 3개 사용된 경우 들은 5가 1번 사용된 경우 들과 2번 사용된 경우 들의 사칙 연산된 값 들의 집합이다.

2번 사용된 경우 들은 1번 사용된 경우를 사칙 연산 한 것이다.

해당 문제에서는 결과 값이 8 이상이라면 -1를 반환하게 하여 그 이상의 연산은 의미 없음을 알려주고 있어,

8개가 사용 되는 경우 까지만 연산 하면 된다.

 

 

해결 코드

//최대 사용 가능 횟수는 8회
//5, 55, 555 ... 55555555가 사칙연산 없이 가능한 숫자.
//3번 사용된 경우의 수는 2번 사용된 경우에 1번 사용된 경우를 사칙연산한 것.
//즉, 이전 횟수의 경우들을 조합하면 다음 횟수의 경우를 만들어 낼 수 있음.


function solution(N, number) {
    var answer = 0;
    let s = [];
    
    for (let i = 1; i<9; i++){
        s.push(new Set());
        let e = "";
        for (let j = 0; j<i; j++){
            e += String(N)
        }
        s[i-1].add(parseInt(e));
    }

    
   // 2 => (1,1)
   // 3 => (1,2)
   // 4 => (1,3) (2,2)
   // 5 => (1,4), (2,3)
    
    for (let i = 0; i<8; i++){
        for (let j = 0; j<i; j++){
            for (let e1 of s[j]){
                   for (let e2 of s[i-j-1]) //e1이 0부터 시작하기때문에 -1을 해줘야 함.
                       {
                           s[i].add(e1 + e2);
                           s[i].add(e1 - e2);
                           s[i].add(Math.floor(e1 / e2));
                           s[i].add(e1 * e2);
                       }
            }
        }
        for (let k of s[i]){
            if(k === number){
                return i+1; //0부터 배열이 시작하므로 +1 후 횟수 반환
            }
        }
    }
    //모두 실패
    return -1;
}