[백준] 계단 오르기, 포도주 시식, RGB거리 (javascript)

 

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

2579번: 계단 오르기

 

 

🤔 해결방법

1. dp 배열 초기화하기 (각 요소 = i번째 계단에 오를 때까지 얻을 수 있는 최대값)
2. dp[1] = arr[1],   dp[2] = arr[1] + arr[2] 로 설정하기
3. 3번째 칸부터는 dp[i - 3] + arr[i - 1] + arr[i]와 dp[i - 2] + arr[i] 이렇게 두 경우 중 최대값 넣어주기

 

 

🔑 풀이

const input = require("fs")
  // .readFileSync("/dev/stdin")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n");

const n = Number(input[0]);
const arr = []; // 계단 점수 담긴 배열
arr.push(0);
for (let i = 1; i <= n; i++) {
  arr.push(Number(input[i]));
}

function solution(n, arr) {
  const dp = new Array(n + 1).fill(0); // i번째 계단에 오를 때까지 얻을 수 있는 최대값
  dp[1] = arr[1];
  dp[2] = arr[1] + arr[2];

  for (let i = 3; i <= n; i++) {
    dp[i] = Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]);
  }
  return dp[n];
}
console.log(solution(n, arr));

 

계단은 최대 두 칸씩 오를 수 있고 마지막 계단은 반드시 포함해야 한다는 규칙이 있다.

이를 바탕으로 모든 경우의 수를 따져보았을 때  밟는 것을 o, 안 밟는 것을 x라고 한다면 다음과 같이 항상 두 가지로 나뉨을 알 수 있다.

~ o x o o => dp[i - 3] + arr[i - 1] + arr[i]

   ~ o x o => dp[i - 2] + arr[i]

따라서 두 경우 중 최대 값을 i번째에 넣어주기만 하면 된다.

 

 

 

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

2156번: 포도주 시식

 

 

🤔 해결방법

1. dp 배열 초기화하기 (각 요소 = i번째까지 마실 수 있는 포도주의 최대양)
2. dp[1] = wine[1],   dp[2] = Math.max(dp[1], wine[1] + wine[2], wine[2]) 로 설정하기
3. 3번째 칸부터는 dp[i - 1], dp[i - 2] + wine[i], dp[i - 3] + wine[i - 1] + wine[i] 이렇게 세 가지의 경우 중 최대값을 넣어주기

 

 

🔑 풀이

const input = require("fs")
  // .readFileSync("/dev/stdin")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n");
const n = Number(input[0]); // 포도주 잔의 개수
let wine = [0]; // 포도주
for (let i = 1; i <= n; i++) {
  wine.push(Number(input[i]));
}

function solution(n, wine) {
  if (n === 1) return wine[1]; // 포도주 잔이 하나뿐인 경우
  const dp = new Array(n + 1).fill(0); // 각 요소 = i번째까지 마실 수 있는 포도주의 최대양
  dp[1] = wine[1];
  dp[2] = Math.max(dp[1], wine[1] + wine[2], wine[2]);

  for (let i = 3; i <= n; i++) {
    dp[i] = Math.max(
      dp[i - 1],
      dp[i - 2] + wine[i],
      dp[i - 3] + wine[i - 1] + wine[i]
    );
  }
  return Math.max(...dp);
}
console.log(solution(n, wine));

 

3번 연속 마시기는 불가하며 i번째에 마실 수도 있고 안 마실 수도 있다는 규칙이 있다.

계단 오르기 문제와 비교하면 i번째에 안 마실 수도 있다는 규칙이 추가된 것을 알 수 있다.

따라서 계단 오르기 문제에서 구했던 두 가지의 경우에 안 마시는 경우만 추가해주면 된다.

i번째에서 안 마시는 경우는 i번째의 최대값이 i-1번째와 같다는 것을 의미하므로 dp[i]에 dp[i - 1]이 들어가게 된다.

 

 

 

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

1149번: RGB거리

 

 

🤔 해결방법

1. dp 배열 초기화하기 (각 요소 = i-1행 중에서 현재 dp[i][j]의 색을 제외한 비용들과 현재 비용의 합 중 가장 적은 비용)

2. 첫째줄은 1번 집의 비용을 그대로 넣기

3. 현재의 색을 제외하고 가능한 경우 중 최대값 넣어주기
4. 마지막 줄에서 최소값 출력하기

 

 

🔑 풀이

const input = require("fs")
  // .readFileSync("/dev/stdin")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n");
const n = Number(input[0]); // 집의 수

let fee = []; // 비용이 담긴 배열
for (let i = 1; i <= n; i++) {
  fee.push(input[i].split(" ").map(Number));
}

function solution() {
  let dp = [fee[0]];
  for (let i = 1; i < n; i++) {
    const arr = new Array(3).fill(0);
    dp.push(arr);
  }

  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.min(dp[i - 1][1] + fee[i][0], dp[i - 1][2] + fee[i][0]); // 빨강
    dp[i][1] = Math.min(dp[i - 1][0] + fee[i][1], dp[i - 1][2] + fee[i][1]); // 초록
    dp[i][2] = Math.min(dp[i - 1][0] + fee[i][2], dp[i - 1][1] + fee[i][2]); // 파랑
  }
  return Math.min(...dp[n - 1]);
}
console.log(solution(n, fee));

 

i번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다는 규칙이 있다.

dp[i][0]는 빨간색을 칠한 경우에 해당되므로 i-1번째에서 초록색을 칠한 경우와 파란색을 칠한 경우 중 최소값을 넣는다.

dp[i][1]는 초록색을 칠한 경우에 해당되므로 i-1번째에서 빨간색을 칠한 경우와 파란색을 칠한 경우 중 최소값을 넣는다.

dp[i][2]는 파란색을 칠한 경우에 해당되므로 i-1번째에서 빨간색을 칠한 경우와 초록색을 칠한 경우 중 최소값을 넣는다.

모든 집을 칠하는 비용의 최솟값을 출력해야 하므로 가장 마지막 줄에서 최소값을 출력해주면 된다.