[JS] DP - N으로 표현

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

 

---

 

solution

function solution(N, number) {
  if (N === number) return 1;
  
  const use = Array.from(new Array(9), (u, i) => {
    u = new Set();
    const NStr = String(N).repeat(i);
    u.add(+NStr);
    return u;
  });
  
  for (let i = 1; i <= 8; i++) {
    for (let j = 1; j < i; j++) {
      for (let first of use[j]) {
        for (let second of use[i - j]) {
          use[i].add(first + second);
          use[i].add(first - second);
          use[i].add(first * second);
          use[i].add(first / second);
        }
      }
    }
    if (use[i].has(number)) return i;
  }
  return -1;
}

크기가 9인 배열 use를 만든다.

조건에서 최솟값이 8보다 크면 -1을 리턴하므로 use의 index를 N의 사용횟수라 본다. (index 0은 사용하지 않음)

i = 1 일 때,  N

i = 2 일 때,  NN, N + N, N - N, N * N, N / N

i = 3 일 때, NNN, i = 1일 때과 i = 2일 때 숫자를 연산

i = 4 일 때, NNNN, i = 1 i = 3, i = 2 i = 2, i = 3, i = 1 일 때 숫자를 연산

...

연산한 값이 number가 되었을 때의 i를 return 하면 정답이 된다.

루프가 도는 동안 연산한 값 중에 number가 없다면 -1을 리턴한다.