백준 2839 다이나믹 프로그래밍

백준 설탕분해 문제이다
3과 5를 더해서 만들 수 있으면 그갯수만큼 출력하고
아닐경우에는 -1를 출력한다.

브루다포스로도 풀 수 있었으나
다이나믹 프로그래밍이 더 좋은 방법으로 생각해서 접근했다.
다이나믹 프로그래밍에 대해 아직 완벽히 이해한 것은 아니지만, 추후 레벨에 맞추어서 공부할 예정이다.

이무

const input = require("fs")
  .readFileSync("20230330/example3.txt")
  .toString()
  .trim()
  .split("\n");

let num = Number(input[0]);

let numArray = new Array(num).fill(0);
numArray[3] = 1;
numArray[5] = 1;

for (let i = 6; i <= num; i++) {
  let tmp = Math.min(numArray[i - 3], numArray[i - 5]);

  if (!tmp) {
    if (!numArray[i - 3] && !numArray[i - 5]) {
      //2개다 0인경우
      numArray[i] = 0;
    } else if (!numArray[i - 3]) {
      numArray[i] = 1 + numArray[i - 5];
    } else if (!numArray[i - 5]) {
      numArray[i] = 1 + numArray[i - 3];
    }
  } else {
    numArray[i] = tmp + 1;
  }
}

if (numArray[num]) {
  console.log(numArray[num]);
} else {
  console.log(-1);
}

//1이 하나인 경우
// 찾아서 1 올려주고 넣어줌

//0이 두개인 경우
//-1 반환

//1이 이상이 두개인 경우
//기존의 것 +1
// 9
// 6은 2임
// 15 12 10
// 12 =4
// 10 = 2;

중요한 포인트는 -1을 마지막에 계산하는 것이었다. 처음에 없는 것은 -1 넣고 계산하였더니 이후 연산이 망가졌고 마지막에 0인 것을 체크하고 -1로 출력하는 방법으로 해결하였다.

또한 경우의 수를 0 두개 0,1 하나인 경우 1 이상이 2개인 경우로 나누어서 생각하는 것이 주효했다.
그리고 작은 수부터 하나씩 채워가며 식을 확인했다.