[백준 2579] 계단 오르기
February 18, 2023
문제
https://www.acmicpc.net/problem/2579
아이디어
각 계단까지의 합을 기록해두고 점차 다음 계단으로 올라가면서 더 높은 합이 나오도록 하면 된다.
먼저 1번째 계단까지의 합은 무조건 [1번째 계단]의 점수가 된다.
2번째 계단까지의 합도 무조건 [1번째 계단의 점수+2번째 계단]의 점수가 된다.
그런데 세 개의 계단을 연달아서 밟을 수는 없으므로 3번째 계단부터는 [1번째 계단+2번째 계단]과 [2번째 계단+3번째 계단] 중에서 더 큰 값이 된다.
그 이후 i번째 계단을 걷는 방법은 두가지인데, 아래 값 중에서 더 큰 값으로 골라주면 된다.
(i-3번째 계단까지의 합) + (i-1번째 계단의 점수) + (i번째 계단의 점수) (i-2번째 계단까지의 합) + (i번째 계단의 점수)
소스코드
// 입력 처리
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const stairs = input.slice(1, input.length).map(item => Number(item));
const sum = Array.from({ length: n }, () => 0);
sum[0] = stairs[0];
sum[1] = stairs[0] + stairs[1];
sum[2] = Math.max(stairs[0] + stairs[2], stairs[1] + stairs[2]);
function solution() {
for (let i = 3; i < stairs.length; i++) {
sum[i] = Math.max(
sum[i-3] + stairs[i-1] + stairs[i],
sum[i-2] + stairs[i]
)
}
console.log(sum[n-1]);
}
// 실행
solution();