boj 17435 - 합성함수와 쿼리

개요

 Boj 17435 - 합성함수와 쿼리는 중첩함수를 미리 계산해놓은 테이블을 갖고 얼마나 빨리 찾도록 구현할 수 있냐의 문제입니다. $f_n(x) = f(f(f(f(...f(x)...))))$ 를 구하는데 최적화하기 위해서 어떻게 사전에 계산해놓을 수 있을까요?

 

그 비결은 $f_{(a+b)}(x) = f_a(f_b(x))$ 에 있습니다. 그리고 몇몇 포인트들만 사전에 계산해두는 것이지요.

설명

 $f_{(a+b)}(x)$ 는 풀어쓰면 $f$가 $a$번 중첩된 $f(f(....(f_b(x))))$로 풀어쓸 수 있습니다. 즉, $f_b(x)$의 값 $B$을 미리 계산해놓는다면 그 값에 단순히 $f_a(B)$를 구하면 최종 함수 값을 알 수 있지요. 

 

 이 문제는 그래서 $f_n(x)$에서 $n$의 2의 거듭제곱 수에 해당하는 값들을 모두 미리 계산해놓습니다. $f_{2n} (x) = f_n(f_n(x))$인 점을 이용하여 $f_1$, $f_2$, $f_4$, .... , $f_{2^n}$ 까지 전부 말이죠.

 

그리고 이진법으로 풀어서 몇 번만 함수값을 태우면 바로 답이 구해지게 되죠. 예를들어, $f_{155}(x)$ 는 $f_{128}(f_{16}(f_8(f_2(f_1(x))))$ 와 같습니다. 

 

 

예제

예제를 통해서 한 번 알아보겠습니다. 백준 예제는 조금 단순한 편이어서 다른 예시를 하나 들겠습니다.

x \ n	$f_1(x)$
1	4
2	1
3	5
4	3
5	2

 

 

$f_2(x)$ 값 구하기

$f_2(x) = f_1(f_1(x))$ 이므로, 단순하게 현재 주어진 $f_1(x)$에 대해서 다시 $f_1(x)$값을 가져오면 됩니다. $f_1(1)$은 $4$이고, 이를 다시 $f_1(x)$에 넣으면 $f_1(4) = 3$이 되겠네요. 따라서 $f_2(1) = 3$ 입니다. 이런 식으로 $f_2(x)$ 를 모두 작성해줍니다.

x \ n	$f_1(x)$	$f_2(x)$
1	4	3
2	1	4
3	5	2
4	3	5
5	2	1

 

$f_4(x)$ 값 구하기

$f_4(x) = f_2(f_2(x))$입니다. 따라서 $f_2(x)$에서 구해진 값 $A$를 갖고 다시 $f_2(A)$를 찾으면 되지요. 예를들어, $f_4(1)$은 $f_2(f_2(1)) = f_2(3) = 2$가 됩니다.

 

x \ n	$f_1(x)$	$f_2(x)$	$f_4(x)$
1	4	3	2
2	1	4	5
3	5	2	4
4	3	5	1
5	2	1	3

 

 

일반화

결국 $f_{2n}(x) = f_n(f_n(x))$ 이므로, 배열을 구성하는데는 arr[x][k] = arr[ arr[x][k-1] ][k-1] 가 됩니다. 

 

$f_6(3)$의 값 구하기

예제로서 $f_6(3)$을 구한다고 가정하면, $f_6(3) = f_4(f_2(3)) = f_4(2) = 1$이 됩니다. $f(x)$를 6번 반복하는 것이 아니라 딱 2번만으로 구했네요.

 

시간복잡도

테이블을 구성하는 과정은 $x$의 범위인 백준 문제상의 변수 $m$에 대해, $[1,m]$의 수 각각의 2의 거듭제곱 함수값을 $n$ (최대 500,000)까지 구해야 하므로 $log n$을 곱하면 됩니다.

 

$O(m log n)$

 

 함수값을 찾는 과정은 $O(log n)$ 입니다. 쿼리 수는 $Q$이므로 최종 시간 복잡도는 $O((m + Q)log n)$ 입니다.

 

코드

 

RUST 코드에 다음과 같은 특이사항이 있습니다.

 * I/O template은 bubbler  님의 풀이를 참조하였습니다.

 * I/O template이 없는 경우에는 동일한 알고리즘이라도 I/O에 의해서 시간 초과가 발생합니다.

 * 아쉽지만 PS에서 많이 쓰이는 언어가 아니라서 감수해야 할 것 같습니다.

C++

#include<stdio.h>

const int logbound = 19;
int lca[200001][logbound];

int main(){
    int m, q;
    scanf("%d ", &m);

    for(int i = 1; i <= m; i++)
        scanf("%d ", &lca[i][0]);

    for(int i = 1; i < logbound; i++)
        for(int j=0; j<=m; j++)
            lca[j][i] = lca[lca[j][i-1]][i-1];

    scanf("%d", &q);
    for(int _q = 0; _q < q; _q++){
        int n, x, unit = 0;
        scanf("%d %d\n", &n, &x);
        while(n > 0){
            if(n % 2){
                x = lca[x][unit];
            }
            n >>= 1;
            unit++;
        }
        printf("%d\n", x);
    }
}

 

RUST

use std::io::{stdin, Read};

const logbound : usize = 19;
fn func<R: BufRead, W: Write>(io: &mut IO<R, W>) -> Option<()> {

    // 1. Input f1
    let m = io.get(0usize)?;
    let mut lca: Vec<Vec<usize>> = vec![vec![0 as usize; logbound]; m+1];
    for _i in 1..(m+1){
        let a = io.get(0usize)?;
        lca[_i as usize][0] = a;
    }

    // 2. build LCA array
    for i in 1..logbound{
        for j in 1..(m+1){
            lca[j][i] = lca[lca[j][i-1]][i-1];
        }
    }

    // 3. Processing Query
    let q = io.get(0usize)?;
    for _q in 0..q{
        let [n, x] = io.get([0usize; 2])?;
        let mut n = n;
        let mut x = x;
        let mut unit = 0;
        while n > 0 {
            if n % 2 == 1{
                x = lca[x as usize][unit];
            }
            n >>= 1;
            unit += 1;
        }
        io.put(x).nl();
    }
    None
}


/// IO template
mod io {
	pub(crate) use std::io::{Write, stdin, stdout, BufWriter, BufRead};
	pub(crate) struct IO<R: BufRead, W: Write> {
		ii: I<R>,
		oo: BufWriter<W>,
	}
	impl<R: BufRead, W: Write> IO<R, W> {
		pub(crate) fn new(r: R, w: W) -> Self {
			Self {
				ii: I::new(r),
				oo: BufWriter::new(w),
			}
		}
		pub(crate) fn get<T: Fill>(&mut self, exemplar: T) -> Option<T> {
			self.ii.get(exemplar)
		}
		pub(crate) fn put<T: Print>(&mut self, t: T) -> &mut Self {
			t.print(&mut self.oo);
			self
		}
		pub(crate) fn nl(&mut self) -> &mut Self {
			self.put("\n")
		}
	}
	pub(crate) trait Print {
		fn print<W: Write>(&self, w: &mut W);
	}
	macro_rules! print_disp {
		($($t:ty),+) => {
			$(impl Print for $t { fn print < W : Write > (& self, w : & mut W) {
			write!(w, "{}", self) .unwrap(); } })+
		};
	}
	print_disp!(usize, i64, String, & str, char);
	pub(crate) struct I<R: BufRead> {
		r: R,
		line: String,
		rem: &'static str,
	}
	impl<R: BufRead> I<R> {
		pub(crate) fn new(r: R) -> Self {
			Self {
				r,
				line: String::new(),
				rem: "",
			}
		}
		pub(crate) fn next_line(&mut self) -> Option<()> {
			self.line.clear();
			(self.r.read_line(&mut self.line).unwrap() > 0)
				.then(|| {
					self
						.rem = unsafe {
						(&self.line[..] as *const str).as_ref().unwrap()
					};
				})
		}
		pub(crate) fn get<T: Fill>(&mut self, exemplar: T) -> Option<T> {
			let mut exemplar = exemplar;
			exemplar.fill_from_input(self)?;
			Some(exemplar)
		}
	}
	pub(crate) trait Fill {
		fn fill_from_input<R: BufRead>(&mut self, i: &mut I<R>) -> Option<()>;
	}
	fn ws(c: char) -> bool {
		c <= ' '
	}
	macro_rules! fill_num {
		($($t:ty),+) => {
			$(impl Fill for $t { fn fill_from_input < R : BufRead > (& mut self, i : &
			mut I < R >) -> Option < () > { i.rem = i.rem.trim_start_matches(ws); while i
			.rem.is_empty() { i.next_line() ?; i.rem = i.rem.trim_start_matches(ws); }
			let tok = i.rem.split(ws).next().unwrap(); i.rem = & i.rem[tok.len()..]; *
			self = tok.parse().ok() ?; Some(()) } })+
		};
	}
	fill_num!(usize, i64, f64);
	impl<T: Fill> Fill for Vec<T> {
		fn fill_from_input<R: BufRead>(&mut self, i: &mut I<R>) -> Option<()> {
			for ii in self.iter_mut() {
				ii.fill_from_input(i)?;
			}
			Some(())
		}
	}
	impl<T: Fill, const N: usize> Fill for [T; N] {
		fn fill_from_input<R: BufRead>(&mut self, i: &mut I<R>) -> Option<()> {
			for ii in self.iter_mut() {
				ii.fill_from_input(i)?;
			}
			Some(())
		}
	}
}
use io::*;
pub fn main() {
	let stdin = stdin().lock();
	let stdout = stdout().lock();
	let mut io = IO::new(stdin, stdout);
	func(&mut io);
}