(Javascript) - 프로그래머스(고득점 kit : 동적계획법) : N으로 표현

programmers.co.kr/learn/courses/30/lessons/42895?language=javascript

코딩테스트 연습 - N으로 표현

backtracking으로 푼 문제였습니다.

 

풀이방법

 모든 경우의 수를 dfs를 사칙연산에 대해 계속 호출하는 방식으로 해결했습니다.

 

Code

let ans = 0x3f3f3f3f;
let n, num;
function dfs(depth, sum) {
  if (depth > 8) return -1;
  if (sum == num) {
    ans = Math.min(ans, depth);
    return;
  }
  let tmp = 0;

  for (let i = 0; i < 8; i++) {
    tmp = tmp * 10 + n;
    dfs(depth + i + 1, sum + tmp);
    dfs(depth + i + 1, sum - tmp);
    dfs(depth + i + 1, sum * tmp);
    dfs(depth + i + 1, parseInt(sum / tmp));
  }
}

function solution(N, number) {
  n = N;
  num = number;
  ans = 0x3f3f3f3f;
  dfs(0, 0);
  if (ans > 8) return -1;
  return ans;
}

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