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

문제풀이

진짜 레벨3에 오면서 dp가 많아지고 dp는 진짜 많은 문제풀이가 답이라고 느껴졌다.
완전 탐색 + 메모제이션을 이용해서 풀어야하는데, 정말 힘들었다.
솔직히 질문하기에서 본 힌트들과 구글링해서 얻은 힌트들이 아니였으면 못 풀었을 것 같다.

1. dep = 1일 때, 즉 N을 한번만 사용하는 경우는, N밖에 없으므로 처리.
2. dep >= 2일 때부터는 N을 사용해서 만들 수 있는 경우의 수를 합쳐주면 된다.
   1. N=2 => N=1 + N=1
   2. N=3 => N=1 + N=2
   3. N=4 => N=1 + N=3 , N=2 = N=2
   4. ...
   5. 여기서, N=3 => N=2 + N=1 는 고려하지 않아야 한다.(똑같기 때문.)
3. 이렇게 경우의 수를 나눈다음,
   1. +,*,-,/에 대해서 실행하면 된다.
   2. 여기서 중요한 포인트는, -와 /는 위치가 바뀌면 값도 바뀌기 때문에 그 경우도 고려해줘야한다.
   3. 그리고 ex. 55, 555 같은 경우는 dep만큼 숫자를 붙이고 그것을 Set에 넣어주면 된다.
4. dep가 8보다 큰 경우는 어차피 -1을 리턴하면 된다.

function solution(N, number) {
  var answer = 0;
  answer = abc(N, number, 0, [0]);
  return answer;
}
function abc(N, target, dep, dp) {
  let total = new Set();
  if (dep > 8) {
    return -1;
  }
  dep++;
  if (dep === 1) {
    total.add(N);
    dp.push(total);
    if (total.has(target)) return dep;
  } else {
    for (let i = 1; i < Math.floor(dep / 2) + 1; i++) {
      for (let j = dep - i; j >= dep - i; j--) {
        dp[i].forEach(e => {
          dp[j].forEach(el => {
            total.add(e + el);
            total.add(e * el);
            total.add(el - e);
            total.add(e - el);
            if (e !== 0) total.add(Math.floor(el / e));
            if (el !== 0) total.add(Math.floor(e / el));
          });
        });
      }
    }
    total.add(Number(`${N}`.repeat(dep)));
    dp.push(total);
    if (total.has(target)) return dep;
  }
  return abc(N, target, dep, dp);
}

아쉬운 점 || 느낀 점

구글링 + 질문하기의 힘을 빌려 풀었지만, 풀긴 풀었다.
뭔가 dp는 dp만의 프로그래밍이 있지 않을까? 라는 생각이 처음에 문제를 못푼 이유 같다.
완전탐색 + 메모제이션을 이용해서 풀면 되는 문제인데, 그 생각을 못했다.
아직 dp에 관해서 정확한 정의를 모르는 것 같다. (공부하자!)