- Today
- Total
Byeo
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);
}
'알고리즘 (Algorihtm) > 백준' 카테고리의 다른 글
boj 11376 - 열혈강호 2 (0) | 2024.01.14 |
---|---|
boj 11014 - 컨닝 2 (0) | 2024.01.11 |
boj 7869 - 두 원 (0) | 2021.12.30 |
boj 7626 - 직사각형 (2) | 2021.12.29 |
boj 1069 - 집으로 (0) | 2021.08.06 |