다이나믹 프로그래밍

🥝 곱하기 혹은 더하기

입력

4
1 3 1 5

◼◼◼ Solution ◼◼◼

4. ...

문제 풀이

// Run by Node.js
const { count } = require("console");
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let inputArr = [];
rl.on("line", function (line) {
  inputArr.push(line);
}).on("close", function () {
  solution();
  process.exit();
});

const solution = () => {
  let arr = [];
  for (let x of inputArr) {
    arr.push(x.split(" "));
  }
  for (let x of arr) {
    for (let i = 0; i < x.length; i++) {
      x[i] = parseInt(x[i]);
    }
  }
  let n = arr[0][0];
  let list = arr[1];
  let dy = Array.from({ length: 100 }, () => 0);
  dy[0] = list[0];
  dy[1] = Math.max(dy[0], list[1]);
  for (let i = 2; i < n; i++) {
    dy[i] = Math.max(dy[i - 2] + list[i], dy[i - 1]);
  }
  console.log(dy[n - 1]);
};

---

🥝 바닥 공사

◼◼◼ Solution ◼◼◼

4. ...

문제 풀이

// Run by Node.js
const { count } = require("console");
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let inputStr = "";
rl.on("line", function (line) {
  inputStr += line;
}).on("close", function () {
  solution();
  process.exit();
});

const solution = () => {
  const n = parseInt(inputStr);
  let dy = Array.from({ length: 1001 }, () => 0);
  dy[1] = 1;
  dy[2] = 3;
  for (let i = 3; i <= n; i++) {
    dy[i] = (dy[i - 1] + dy[i - 2] * 2) % 796.796;
  }
  console.log(dy[n]);
};

구현할 때 개선점

• 한 줄 평
  More Info: 벨로그 링크

---

🥝 효율적인 화폐 구성

입력

2 15
2
3

3 4
3
5
7

◼◼◼ Solution ◼◼◼

4. ...

문제 풀이

// Run by Node.js
const { count } = require("console");
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let inputArr = [];
rl.on("line", function (line) {
  inputArr.push(line);
}).on("close", function () {
  solution();
  process.exit();
});

const solution = () => {
  let firstLine = inputArr[0].split(" ");
  let [n, m] = [parseInt(firstLine[0]), parseInt(firstLine[1])];
  let coins = [];
  for (let i = 1; i <= n; i++) {
    coins.push(parseInt(inputArr[i]));
  }
  let d = Array.from({ length: m + 1 }, () => 10001);
  d[0] = 0;
  for (let i = 0; i < n; i++) {
    for (let j = coins[i]; j < m + 1; j++) {
      if (d[j - coins[i]] !== 10001) {
        d[j] = Math.min(d[j], d[j - coins[i]] + 1);
      }
    }
  }
  if (d[m] == 10001) console.log(-1);
  else console.log(d[m]);
};

구현할 때 개선점

• 한 줄 평
  More Info: 벨로그 링크

---

🥝 곱하기 혹은 더하기

입력

◼◼◼ Solution ◼◼◼

4. ...

문제 풀이

구현할 때 개선점

• 한 줄 평
  More Info: 벨로그 링크

---