썸네일 출처: https://ye-yo.github.io/thumbnail-maker/
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까지 계산한 뒤 마지막 값들 중 최댓값을 고르면 된다.
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());
}