[JS] 2579_계단오르기

문제

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

 

풀이

처음 이 문제를 풀때는 BFS로 접근했지만 나는 풀이 방법을 찾지 못했다... 시간초과 에러가 발생했다....

 

그래서 순수하게 동적 계획법을 사용해 풀이하기로 결정했다.

 

이 문제를 잘 보면 특정 패턴이 보일 것이다. n 번째에 도달하는 방법은 두가지가 있다. 첫 번째로는 n-1 번째에서 한칸 뛰어넘어 온 경우이고, 두 번째는 n-2 번째에서 두칸을 넘어온 경우이다. 이때 두칸을 넘어온 경우는 문제가 되지 않지만, 한 칸을 넘어온 경우는 3칸을 연속해서 넘으면 안된다는 제한이 있다.

 

위와 같은 제한을 피하는 방법은 n-3칸에서 두칸 넘고 n-1칸에서 한칸 넘는 방법이 있다.

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => +e);

const y = input.shift();
const map = input;

const dp = Array.from({ length: y }, () => 0);

dp[0] = map[0];
dp[1] = Math.max(map[0] + map[1], map[1]);
dp[2] = Math.max(map[1], map[0]) + map[2];

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

console.log(dp[y - 1]);