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

문제

N으로 표현

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

 

 

풀이

설명

N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 구하는 문제입니다.

 

dp를 사용해 해결할 수 있습니다.

 

dp[i]는 N을 i번 사용해서 만들 수 있는 수들의 모음입니다.

N을 i번 사용해서 만든 수, dp[j]와 dp[i - j]의 조합으로 생성될 수 있습니다. (1 <= j < i)

 

점화식은 다음과 같습니다.

점화식

 

예시 코드

function solution(N, number) {
  const MAX_N_LIMIT = 8;
  const dp = Array.from({ length: MAX_N_LIMIT + 1 }, () => new Set());

  for (let i = 1; i <= MAX_N_LIMIT; i++) {
    dp[i].add(Number(String(N).repeat(i)));

    for (let j = 1; j < i; j++) {
      for (const a of dp[j]) {
        for (const b of dp[i - j]) {
          dp[i].add(a + b);
          dp[i].add(a - b);
          dp[i].add(a * b);
          if (b != 0) dp[i].add(Math.floor(a / b));
        }
      }
    }
    if (dp[i].has(number)) return i;
  }

  return -1;
}