프로그래머스 N으로 표현 JavaScript
2023년 3월 1일
문제 풀이
배열 dp에 N 사용 횟수에 따른 값들을 저장한다.
최솟값이 8보다 클 순 없으니 dp의 크기를 9로 정한다.(인덱스 0은 사용하지 않고 1~8까지만 사용) 또한 중복된 값을 피하기 위해 Set 객체를 이용한다.
점화식을 알기 위한 예로 N = 5일 때를 보면,
index.md
dp[1] = 5
dp[2] = 55 + (dp[1]과 dp[1]의 사칙연산한 값들)
dp[3] = 555 + (dp[1]과 dp[2], dp[2]와 dp[1]의 사칙연산한 값들)
dp[4] = 5555 + (dp[1]과 dp[3], dp[2]와 dp[2], dp[3]과 dp[2]의 사칙연산한 값들)
...
즉 점화식은
index.md
dp[n] = (N이 n 만큼의 길이) + (dp[1]과 dp[n-1], dp[2]와 dp[n-2],
...,
dp[n-2]와 dp[2], dp[n-1]과 dp[1]의 사칙연산한 값들)
N의 개수 중 최솟값을 구하는 문제이므로 number를 찾으면 즉시 종료한다.
solution.js
function solution(N, number) {
let answer = -1;
const dp = new Array(9).fill().map(_ => new Set());
for (let i = 1; i <= 8; i++) {
let temp = String(N);
for (let j = 1; j < i; j++) {
temp += N;
}
dp[i].add(Number(temp));
for (let j = 1; j <= i-1; j++) {
for (const left of dp[j]) {
for (const right of dp[i-j]) {
dp[i].add(left + right);
dp[i].add(left - right);
dp[i].add(Math.floor(left / right));
dp[i].add(left * right);
}
}
}
if (dp[i].has(number)) {
answer = i;
break;
}
}
return answer;
}