썸네일 출처: https://ye-yo.github.io/thumbnail-maker/

---

📖 문제

2579번: 계단 오르기

---

💡 아이디어

1. 계단을 1칸 오를 수 있는 횟수에 따라 부분계산하기

i번째 계단을 밟았을 때 앞으로 계단을 한 칸 오를 수 있는 횟수는 1번(이전에 두 칸 뛰었을 때) 또는 0번(이전에 한 칸 뛰었을 때)이다.

i번째 계단을 밟은 후 1칸 오를 수 있는 횟수가 j번 남았을 때 점수의 최댓값을 [i,j]라고 하고, 각 계단의 점수를 N[i]라고 하면 이전에 두 칸을 뛰었는지, 한 칸을 뛰었는지에 따라 다음과 같은 식이 성립한다.

한 칸 뛰었을 때: [i,0] = [i-1,1] + N[i]
두 칸 뛰었을 때: [i,1] = MAX([i-2,0], [i-2,1]) + N[i]

한 칸을 뛰었다면 이전에 한 칸 뛸수 있는 횟수가 1이었다는 의미이고, 뛴 다음 1칸 뛸 수 있는 횟수가 0이 되었다는 뜻이다.

두 칸을 뛰었다면 이전에 한 칸 뛸수 있는 횟수가 몇번 남았던지 다시 1으로 초기화된다.

이것을 그림으로 표현하면 다음과 같다.

이 방식으로 i=2 부터 n-1까지 계산한 뒤 마지막 값들 중 최댓값을 고르면 된다.

2. i=0, 1일 때

i=0일때는 반드시 이전에 한 칸 밟아서 올라왔어야 하고, i=1일때는 처음부터 두 칸 뛰어 올라왔거나 첫 번째 칸을 밟은 뒤 두 번째 칸도 밟은 것이다. 따라서 다음과 같다.

[0,0] = 불가능,
[0,1] = N[0],
[1,0] = [0,1] + N[1],
[1,1] = N[1]

---

⏱️ 최적화

부분계산값을 계산하는 순서와 입력값을 입력받는 순서가 동일하다.
따라서 입력과 계산을 따로 수행할 필요 없이 동시에 수행하면 된다.

또 벡터 대신에 n의 최대 길이를 가진 배열을 사용하면 속도를 더 향상시킬 수 있다.

---

✏️ 코드

use std::cmp::{max, min};
use std::io::{stdin, Read, Write, stdout, BufWriter};

const N_MAX: usize = 300;

fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<usize>);
    let n = input.next().unwrap();
    let mut scores = [[0usize; 2]; N_MAX];
    scores[0][1] = input.next().unwrap();
    if n == 1 {
        println!("{}", scores[0][1]);
        return;
    }
    let score = input.next().unwrap();
    scores[1][1] = score;
    scores[1][0] = scores[0][1] + score;
    for i in 2..n {
        let score = input.next().unwrap();
        scores[i][0] = scores[i-1][1] + score;
        scores[i][1] = *scores[i-2].iter().max().unwrap() + score;
    }
    println!("{}", *scores[n-1].iter().max().unwrap());
}