다이나믹 프로그래밍

https://www.acmicpc.net/problem/2839

 

일단 dy라는 다이나믹 배열을 만들겠습니다.

그리고 그 안에 1부터 5까지는 미리 세팅해 두겠습니다.

그리고 6부터 시작해서 처음에는 왼쪽 다섯칸 가서 dy[1]이 0보다 크다면 d[6] = dy[1] + 1을 해줍니다.

만약 dy[1]이 -1이라면 두번째로 dy[6]에서 왼쪽으로 세칸을 가서 dy[3]이 0보다 크다면 dy[6] = dy[3] + 1을 해줍니다.

만약 dy[3]도 -1이라면 dy[6] = -1을 해줍니다.

이렇게 예제에 입력된 대로 18까지 이 로직을 반복해주면 아래의 dy배열처럼 각 자릿값에 숫자가 들어갈 것입니다.

마지막으로 dy[18]을 출력해주면 됩니다.

 

 

소스코드로 재현해 보겠습니다.

 

var fs = require('fs'); 
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0])

function solution(n) {
  let answer = 0;
  let dy = Array.from({length: n+1}, () => 0);
  dy[1] = -1;
  dy[2] = -1;
  dy[3] = 1;
  dy[4] = -1;
  dy[5] = 1;
  for (let i = 6; i <=n; i++) {
    if(dy[i-5] > 0) dy[i] = dy[i-5] + 1
    else if(dy[i-3] > 0) dy[i] = dy[i - 3] + 1;
    else dy[i] = -1
  }
  answer = dy[n]
  return answer
}

console.log(solution(n))