[BOJ 2579] 계단 오르기

문제

계단 오르기

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

 

 

풀이

설명

계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 문제입니다.

 

규칙은 다음과 같습니다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있습니다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다다음 계단으로 오를 수 있습니다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 됩니다. 단, 시작점은 계단에 포함되지 않습니다.
3. 마지막 도착 계단은 반드시 밟아야 합니다.

 

DP를 통해 해결할 수 있습니다.

 

dp[i]는 i번째 계단까지 밟았을 때 얻을 수 있는 최대 점수입니다.

 

계단에 써있는 점수를 담은 배열을 stairs라고 할 때,

dp[i]의 값은 다음 두 가지 중 더 큰 값입니다.

• dp[i - 2] + stairs[i]
• dp[i - 3] + stairs[i - 1] + stairs[i]

 

예시 코드

function solution() {
  const n = Number(input());
  const stairs = [0].concat(Array.from({ length: n }, () => Number(input())));
  const dp = [0, stairs[1], stairs[1] + stairs[2]];

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

  return dp[n];
}