[백준] 2579: 계단 오르기 - JS (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

  접근 방식

 

dp 배열에는 각 계단으로 갈 때 까지의 최대 점수를 저장한다.

 

예를 들어, 점수가 stairs = [10, 20, 15, 25, 10, 20]인 계단이 존재한다면 dp[1] = 10, dp[2] = 30, dp[3] = 35 ... ... 이렇게 저장하는 것이다. 

 

규칙을 정리해 본다면, 

n번 째 계단으로 가는 방식은 두 가지 존재한다. 

1. dp[n-2] + stairs[n - 1] (두 계단을 오른 경우)
2. dp[n-3] + stairs[n - 2] + stairs[n - 1] (두 계단을 오르고 한 계단을 올랐을 경우)

그리고 우리는 이 두 가지 중에서 더 큰 값을 선택해서 dp[n]에 저장하면 된다.

 

 

  풀이

 

 

const fs = require('fs');
const [n, ...arr] = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(Number);


const dp = new Array(n + 1).fill(0);

dp[1] = arr[0];

dp[2] = arr[0] + arr[1];

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

console.log(dp[n])