N 으로 표현

문제

풀이

코드

function solution(N, number) {
  if (N == number) return 1; //애초에 같을 경우 1 리턴

  // 전체 집합 공간 할당
  const dp = [...Array(9)].map(() => new Set());
  let ans = -1; // 순회 다 돌아도 값이 없을 경우 -1 리턴
  let stringN = String(N);

  dp[1].add(N);

  for (let i = 2; i <= 8; i++) {
    // i에 대한 집합 만들기
    stringN += N; // 55,555,5555... 넣어두기
    dp[i].add(Number(stringN));

    for (let j = 1; j < i; j++) {
      for (const num1 of dp[i - j]) {
        for (const num2 of dp[j]) {
          dp[i].add(num1 + num2); //dp 배열의 2 ~ 8 을 채운다 (집합 구성요소) 사칙연산 (집합 구성요소)
          dp[i].add(num1 - num2);
          dp[i].add(num1 * num2);
          dp[i].add(num1 / num2);
        }
      }
    }
    // i집합에 number가 포함되어 있다면 i가 정답
    if (dp[i].has(number)) {
      ans = i;
      break;
    }
  }
  return ans;
}

//배열 만들어서 1부터 N까지 만드는 수의 최솟 값을 담자!
//N의 최소 사용횟수가 8번보다 크면 -1을 반환하도록 제한되어있으므로
//"N을 1번 사용하는 것에서부터 8번사용하는 것까지를 순차적으로 숫자를 만들어보고",
//1번부터 8번 집합에 각각 저장!! 그리고 number가 만들어졌는지 확인!!

//N이 5일때 5는 N을 1번 사용한 것이고, 55는 2번, 555는 3번, 5555는 4번, 55555555는 8번 사용한 것
//이를 각각의 집합에 미리 추가

//1번 집합에 들어갈 수 있는 숫자는 5 하나 밖에 없음.
//2번 집합에는 55외에 들어갈 수 있는 숫자가 있습니다. N + N, N-N, N*N, N/N. 즉, 1번 구성요소로 사칙연산을 한 것
// 요기 아래부터 중요 !!
//"3번 집합의 구성은 555 & ( 1번집합의 구성요소 +-*/ 2번집합의 구성요소),  ( 2번집합의 구성요소 +-*/ 1번집합의 구성요소)" 입니다.
//4번 집합의 구성은 5555와 ( 1번집합의 구성요소 +-*/ 3번집합의 구성요소),  ( 2번집합의 구성요소 +-*/ 2번집합의 구성요소),  ( 3번집합의 구성요소 +-*/ 1번집합의 구성요소) 입니다.

//결과
//만들어진 숫자 중 타겟인 number이 발견되면 바로 집합 번호를 반환
//순회가 모두 끝난 후에도 number를 발견하지 못했다면, 최소횟수가 8이상인 것이므로 -1를 반환

console.log(solution(5, 12));
console.log(solution(2, 11));