[프로그래머스💯] 코딩테스트 연습 > 동적 계획법 > N으로 표현 (JavaScript)

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

const cached = Array(10)
  .fill(null)
  .map(() => Array())

function N_n(N, n) {
  let answer = 0
  for (let i = 0; i < n; i++) {
    answer += Math.pow(10, i) * N
  }
  return answer
}

function allCase(N, n) {
  const Nn = []
  if (n === 1) {
    return [N]
  }
  if (cached[N][n]) {
    return cached[N][n]
  }
  Nn.push(N_n(N, n))
  for (let i = 1; i <= parseInt(n / 2); i++) {
    allCase(N, n - i).map(v1 => {
      allCase(N, i).map(v2 => {
        if (v1 !== 0) Nn.push(parseInt(v2 / v1, 10))
        if (v2 !== 0) Nn.push(parseInt(v1 / v2, 10))
        Nn.push(v1 * v2)
        Nn.push(v1 - v2)
        Nn.push(v1 + v2)
        Nn.push(v2 - v1)
      })
    })
  }
  cached[N][n] = Nn
  return Nn
}

function solution(N, number) {
  for (let i = 1; i < 9; i++) {
    if (allCase(N, i).includes(number)) {
      return i
    }
  }
  return -1
}

 

 

풀이)

이문제는 number이 주어지면, number이 최소 몇번안에 가능한지 찾는 방식보다,

미리 주어진 N 을 8개 이용하여 만들수 있는 모든 수를 구해놓고,

그 구해놓은 모든 수안에 number가 있는지를 탐색하는 방법이 더 쉽습니다!

 

N_n 함수 : 숫자를 붙인 숫자 반환 (Ex.  N_n(7,3) = 777)

allCase 함수 : 숫자 N 을 n번 이용해서 만들 수 있는 모든 숫자들의 배열

cached 배열 : allCase 결과 배열들을 모아놓을 캐쉬배열

solution 함수 : allCase 함수를 이용해 최소 몇번째 n 에 number가 출현하는지를 구해냅니다.

 

예) N 은 5, number 은 12 로 주어졌을 때, 우리는 미리 구해놓은 배열을 이용해  12가  allCase(5, 4) 에 가장 먼저 존재한다는 것을 알 수 있습니다. 따라서 정답은 4가 됩니다.

 

• allCase함수에 대한 설명

분할정복을 통해 가능한 모든 케이스를 구해냅니다.

6을 7번이용해서 만들 수 있는 모든 수는

6을 1번 이용한수들 <-> 7을 6번 이용한 수들

6을 2번 이용한수들 <-> 7을 5번 이용한 수들

6을 3번 이용한수들 <-> 7을 4번 이용한 수들

이렇게 짝을지어 연산해서 구할 수 있습니다.

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges