[백준] 2579번 계단 오르기 (JavaScript)

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

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

let N = input.shift();
let answer = [input[0], input[0]+input[1], Math.max(input[0], input[1])+ input[2]];

for(let i = 3; i < N; i++){
	answer[i] = Math.max(answer[i-2] + input[i], answer[i-3] + input[i-1] + input[i]);
}

console.log(answer[N-1]);

 

마지막 계단을 오르기 전까지의 최댓값 + 마지막 계단 값 = 총점수의 최댓값이다.

마지막 계단을 오를 수 있는 경우의 수는 2가지이다.

1. o o x o   

2. o x o o

이유는 3개의 연속된 계단은 밟으면 안 되는 것과  (ex. x o o o)  마지막 계단은 무조건 밟아야 하기 때문이다.

 

따라서 

1. o o x o =====> answer[i - 2] + input[i]

2. o x o o =====> answer[i - 3] + input[i - 1] + input [i]

 

이 두 개의 값 중 최댓값을 구하면 정답이다.