Solution

Memo

  • 점화식을 세우는 전형적인 dp 문제
  • n이 홀수면 채울 수 없으므로 바로 0 출력
  • n = 2일 때 기본 케이스는 3가지
  • n = 4일 때는 기본 케이스 3 * dp[2] + 특이 케이스(2) 1개 → 총 11개
  • 점화식은 dp[n] = dp[n - 2] * 3 + (dp[n - 4] + dp[n - 6] + … + dp[0]) * 2 와 같음
  • 특이 케이스는 n이 4 이상일 때부터 등장하며, 매번 2씩 곱해진다
  • dp[0] = 1을 기준으로 초기값 설정하는 것이 핵심 (dp[0]은 안씀)
  • 반복문은 짝수 단위로만 진행되어야 하므로 step_by(2) 사용해야 한다
// Baekjoon - 2133
// https://www.acmicpc.net/problem/2133

use std::io::{self, Read, Write};

fn main() {
    let mut stdin = io::stdin().lock();
    let mut stdout = io::stdout().lock();
    let mut input = String::new();
    stdin.read_to_string(&mut input).unwrap();
    let mut lines = input.lines();

    let n: usize = lines.next().unwrap().parse().unwrap();

    if n % 2 != 0 {
        writeln!(stdout, "0").unwrap();
        return;
    }

    let mut dp = vec![0; n + 1];
    dp[0] = 1;
    dp[2] = 3;

    for i in (4..=n).step_by(2) {
        dp[i] = dp[i - 2] * 3;
        for j in (0..=i - 4).step_by(2) {
            dp[i] += dp[j] * 2;
        }
    }

    write!(stdout, "{}", dp[n]).unwrap();
}