1️⃣ 문제
2️⃣ 문제 해결 전략
3️⃣ 코드 및 설명
내 코드
function solution(nums) { let count = nums.length - 2; let answer = 0; for (let i = 0; i < count; i++) { var max = Math.max(...nums.slice(1, nums.length - 1)); var maxIdx = nums.indexOf(max); var [leftIdx, rightIdx] = [maxIdx - 1, maxIdx + 1]; while (leftIdx > 0 && nums[leftIdx] === 0) { leftIdx--; } while (rightIdx < nums.length - 1 && nums[rightIdx] === 0) { rightIdx++; } answer += nums[leftIdx] * nums[maxIdx] * nums[rightIdx]; nums[maxIdx] = 0; } return answer; } console.log(solution([10, 1, 50, 50, 20, 5]));
모범 코드
function solution(nums) { const n = nums.length; // dp[l][r]: l~r 사이(l, r는 남겨놓고) 다 제거했을 때 최소점수 const dp = Array.from({ length: n }, () => Array(n).fill(0)); // 구간의 길이는 최소 3이어야 카드를 뺄 수 있음 for (let len = 3; len <= n; len++) { for (let l = 0; l <= n - len; l++) { let r = l + len - 1; dp[l][r] = Infinity; // k는 l+1 ~ r-1 카드 중에서 뽑을 위치 for (let k = l + 1; k < r; k++) { let cost = dp[l][k] + dp[k][r] + nums[l] * nums[k] * nums[r]; if (cost < dp[l][r]) dp[l][r] = cost; } } } return dp[0][n - 1]; }