[TIL] 20210620 - 항해 14일차

미뤄뒀던 일들(안경고치기, 머리 자르기 등)을 열심히 수행하는 주말이었다.
알고리즘 두 문제와 WIL을 쓰고나니 하루가 끝나버렸다.

오늘 공부한 것

BAEKJOON ONLINE JUDGE(BOJ)

• 9184 신나는 함수 실행
• 9461 파도반 수열
• (1149 RGB거리 → 실패)

알고리즘을 풀며 느낀 것 & 생각

어제 9184 신나는 함수 실행을 풀면서 3차원 배열을 만들기가 싫었던 것 같다.
방법을 모른다기보다는 굉장히 귀찮아질 것 같은 강한 예감에 지레 겁먹었다.

하지만 막상 3차원 배열로 풀자 금방 끝나는 문제... 많은 시간을 허공에 날렸다.

오늘 만난 난제는 1149 RGB거리다.

별 생각 없이 백트래킹 방식으로 풀었더니 시간초과가 났다.

const [n, ...ary] = ["3", "26 40 57", "49 60 57", "13 89 99"];

for (let i = 0; i < Number(n); i++) {
  ary[i] = ary[i].split(" ").map((cost) => Number(cost));
}

const stack = [];
let minCost = 0;
let sum = 0;
let previousIndex; // 0이면 RED / 1이면 GREEN / 2이면 BLUE

function getMinCost(depth, n, ary) {
  if (depth === n) {
    if (minCost === 0) minCost = sum;
    else minCost = sum < minCost ? sum : minCost;
    return;
  }

  for (let i = 0; i < n; i++) {
    if (i !== previousIndex) {
      stack.push(i);
      previousIndex = i;
      sum += ary[depth][i];
      getMinCost(depth + 1, n, ary);
      previousIndex = stack.pop();
      sum -= ary[depth][i];
    }
  }
}

getMinCost(0, Number(n), ary);

console.log(minCost);

이 친구도 동적계획법인가 싶은데.. 점화식을 찾지 못했다.
내일 오전 중에 풀어내는 것이 목표다💪🏻