[Level2] 삼각달팽이, DP 막대기

in 코딩테스트 on 프로그래머스




삼각달팽이

프로그래머스

나의 풀이

function solution(n) {
  const answer = new Array(n).fill().map((_, i) => new Array(i + 1));

  let count = 0;
  let x = -1;
  let y = 0;
  while (n > 0) {
    for (let i = 0; i < n; i++) answer[++x][y] = ++count;
    for (let i = 0; i < n - 1; i++) answer[x][++y] = ++count;
    for (let i = 0; i < n - 2; i++) answer[--x][--y] = ++count;
    n -= 3;
  }

  return answer.flat();
}

규칙성을 발견하면 간단한 문제였다. 아래 > 오른쪽 > 위 로 올라가면서 각각 횟수가 1씩 감소한다는 것 이렇게 3번 과정이 계속 반복된다는 것

이 규칙성을 발견하기 전까지는 굉장히 많은 삽질을 했다..ㅎ



동적 프로그래밍

  • 동적인 테이블은 만든다.
  • 기억하기 프로그래밍
  • 분할정복 + 메모이제이션


막대기 자르기 문제

막대기를 가장 높은 가격이 나오게끔 자르기

길이 : 0 1 2 3 4 5 6 7 8 9 10

가격 : 0 1 5 8 9 10 17 17 20 24 30

ex) 길이가 4인 막대기는 2+2로 나누어서 10일때가 가장 비싸다.

막대기

function dpEx(n) {
  const price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30];
  const maxPrice = [0];
  for (let i = 1; i <= n; i++) {
    let target = -1;
    for (let j = 1; j <= i; j++) {
      target = Math.max(target, price[j] + maxPrice[i - j]);
    }
    maxPrice[i] = target;
  }
  return maxPrice[n];
}

console.log(dpEx(2)); //5
console.log(dpEx(3)); //8
console.log(dpEx(4)); //10
console.log(dpEx(7)); //18

dp 문제는 감이 도저히 안잡혀서 오늘부터 주말 특강으로 dp를 정복해보고자 한다.
위 코드와 과정은 이해했지만, 저렇게 생각하는 방식이 아직 익숙하지 않다.
계속 반복하면 익숙해지겠지!!

(참고로 위 문제와 풀이는 제로초님의 블로그글을 참조했습니다.)