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

---

📖 문제

9184: 신나는 함수 여행

---

💡 아이디어

1. 재귀함수의 부분 계산값 저장해두기

문제가 딱 보기에 재귀함수로 풀기 쉬워 보인다. 그래서 완전히 동적계획법으로 풀기 전에 약간의 변형을 준 방법을 생각해봤다.

기본적으로는 재귀적으로 풀되, 변수 a, b, c, 를 인덱스로 가지는 3차원 배열을 만들어서 부분 계산값을 저장해두고 이미 계산한 값이면 또 계산하지 않도록 하는 방식이다.

일반적인 동적계획법과 거의 비슷하지만 동적계획법이 처음부터 끝까지 순차적으로 부분 계산값을 계산해 나가는 반면에 이 방식은 구해야 하는 값부터 시작해서 필요하면 저장된 배열에서 빼서 쓰는 방식이다. 동적계획법이 상향식이라면 이 방식은 하향식이라고 할 수 있을 것 같다.

저장해야 하는 범위가 0 < a, b, c <= 20 이기 때문에 배열의 크기는 20 x 20 x 20 = 8000으로 충분히 만들만 한 사이즈이다.

그 결과, 다음과 같은 재귀함수 코드가 나왔다.

fn w(a: i32, b: i32, c: i32, matrix: &mut [[[i32; MATRIX_SIZE]; MATRIX_SIZE]; MATRIX_SIZE]) -> i32 {
    if a <= 0 || b <= 0 || c <= 0 {
        let a = min(max(0, a), 20);
        let b = min(max(0, b), 20);
        let c = min(max(0, c), 20);
        if matrix[a as usize][b as usize][c as usize] == 0 {
            matrix[a as usize][b as usize][c as usize] = 1;
        }
        1
    } else if a > 20 || b > 20 || c > 20 {
        if matrix[20][20][20] == 0 {
            let n = w(20, 20, 20, matrix);
            matrix[20][20][20]= n;
            n
        } else {
            matrix[20][20][20]
        }
    } else if a < b && b < c {
        let v = if matrix[a as usize][b as usize][(c-1) as usize] == 0 {
            let n = w(a, b, c-1, matrix);
            matrix[a as usize][b as usize][(c-1) as usize] = n;
            n
        } else {
            matrix[a as usize][b as usize][(c-1) as usize]
        };
        let x = if matrix[a as usize][(b-1) as usize][(c-1) as usize] == 0 {
            let n = w(a, b-1, c-1, matrix);
            matrix[a as usize][(b-1) as usize][(c-1) as usize] = n;
            n
        } else {
            matrix[a as usize][(b-1) as usize][(c-1) as usize]
        };
        let y = if matrix[a as usize][(b-1) as usize][c as usize] == 0 {
            let n = w(a, b-1, c, matrix);
            matrix[a as usize][(b-1) as usize][c as usize] = n;
            n
        } else {
            matrix[a as usize][(b-1) as usize][c as usize]
        };
        v + x - y
    } else {
        let v = if matrix[(a-1) as usize][b as usize][c as usize] == 0 {
            let n = w(a-1, b, c, matrix);
            matrix[(a-1) as usize][b as usize][c as usize] = n;
            n
        } else {
            matrix[(a-1) as usize][b as usize][c as usize]
        };
        let x = if matrix[(a-1) as usize][(b-1) as usize][c as usize] == 0 {
            let n = w(a-1, b-1, c, matrix);
            matrix[(a-1) as usize][(b-1) as usize][c as usize] = n;
            n
        } else {
            matrix[(a-1) as usize][(b-1) as usize][c as usize]
        };
        let y = if matrix[(a-1) as usize][b as usize][(c-1) as usize] == 0 {
            let n = w(a-1, b, c-1, matrix);
            matrix[(a-1) as usize][b as usize][(c-1) as usize] = n;
            n
        } else {
            matrix[(a-1) as usize][b as usize][(c-1) as usize]
        };
        let z = if matrix[(a-1) as usize][(b-1) as usize][(c-1) as usize] == 0 {
            let n = w(a-1, b-1, c-1, matrix);
            matrix[(a-1) as usize][(b-1) as usize][(c-1) as usize] = n;
            n
        } else {
            matrix[(a-1) as usize][(b-1) as usize][(c-1) as usize]
        };
        v + x + y - z
    }
}

// what the...

각 부분 계산값마다 이미 저장소에 있는지 확인하고, 있으면 가져오고 없으면 재귀적으로 함수를 후출하는 과정이 있어야 하기 때문에 이렇게 긴 코드가 나왔다. 더 짧게 줄일 수 있는 방식이 있을지도 모르지만, 그다지 교양있는 방식은 아닌 것은 분명하다.

신기한 것은 성능상으로는 일반적인 동적계획법으로 푼 것과 그다지 다르지 않았다는 것이다.

2. 일반적인 동적 계획법

이번엔 낮은 인덱스부터 부분계산값을 구해나가는 방식으로 풀었다.

앞에서처럼 a, b, c를 각 인덱스로 가지는 3차원 배열을 만든 후에, 3중 루프로 낮은 인덱스부터 값을 계산해가며 테이블을 모두 채운 후에 각 테스트 케이스를 입력받고 렌덤 엑세스로 결과값을 출력했다.

부분 계산값이 각 인덱스의 바로 이전 인덱스값에 의존하고 있기 때문에, 테이블을 찾아야 하는 값인 1부터 시작하는 것이 아니라 0부터 시작하게 했다. 이렇게 하면 맨 첫째줄부터 같은 로직을 적용할 수 있어서 코드를 짜기가 더 쉽다.

그 결과, 훨씬 보기 좋고 간단한 코드가 완성되었다.

---

⏱️ 최적화

출력해야 하는 테스트 케이스가 생각보다 많았다. 이걸 간과하고 모든 출력을 println!()매크로를 사용했더니 미친듯한 성능 저하가 생겼다. 이걸 모르고 로직에 문제가 있나 생각해서 괜히 시간만 버렸다.

대신 StdOut에 연결된 BufWriter와 writeln!()매크로를 이용해서 성능을 최적화했다.

// 기존 코드
    loop {
    	... set a, b, c
        println!("w({a}, {b}, {c}) = {}", ...output data);
    }
// 최적화 코드
    let stdout = stdout();
    let mut writer = BufWriter::new(stdout);
    loop {
        ... set a, b, c
        writeln!(writer, "w({a}, {b}, {c}) = {}", ...output data).unwrap();
    }

---

✏️ 코드

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

const MATRIX_SIZE: usize = 21;

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::<i32>);

    let mut matrix = [[[1; MATRIX_SIZE]; MATRIX_SIZE]; MATRIX_SIZE];

    for a in 1..=20 {
        for b in 1..=20 {
            for c in 1..=20 {
                if a < b && b < c {
                    matrix[a][b][c] = matrix[a][b][c-1] + matrix[a][b-1][c-1] - matrix[a][b-1][c];
                } else {
                    matrix[a][b][c] = matrix[a-1][b][c] + matrix[a-1][b-1][c] + matrix[a-1][b][c-1] - matrix[a-1][b-1][c-1];
                }
            }
        }
    }

    let stdout = stdout();
    let mut writer = BufWriter::new(stdout);
    loop {
        let a = input.next().unwrap();
        let b = input.next().unwrap();
        let c = input.next().unwrap();
        if a == -1 && b == -1 && c == -1 {
            break;
        }
        writeln!(writer, "w({a}, {b}, {c}) = {}",
            if a <= 0 || b <= 0 || c <= 0 {
                matrix[0][0][0]
            } else if a > 20 || b > 20 || c > 20 {
                matrix[20][20][20]
            } else {
                matrix[a as usize][b as usize][c as usize]
            }
        ).unwrap();
    }
}