백준 31741번: 구간 덮기 (Python, Rust)

문제링크

https://www.acmicpc.net/problem/31741

문제 총평

- 문제 안에 답이있다.

- 문제를 보고 이분탐색은 떠올렷는데 어떻게 쓰는 거지? 라고 생각하신 분들과 이게 왜 이분탐색이지? 라고 생각하신 분들에게 도움이 되었으면 좋겟습니다.

 

문제 접근방식

- 이 문제에서 가장 중요한 점은 " 최대 3개 사용하여 모두 덮으려 한다." 라는 구절입니다.

- 또한 문제에서 반드시 양쪽을 포함하는 두 선분을 포함해야 합니다. -> a <= S인 선분과 b >= E인 선분 두개가 반드시 있어야 합니다.

- 이 구절에서 최대 3개가 가장 중요한데 그 이유는 간단합니다.

- 다음 문제에서 모든 구간을 겹칠 수 있는 방식은 3개 입니다

1. 한 개의 선분이 전 구간을 덮는 경우 a <= S, b >= E -> 이 경우에는 무조건 오차가 0입니다.

2. 두개의 선분(양쪽 극단을 가지는 두 선분)이 전 구간을 덮는 경우 

3. 두개의 선분(양쪽 극단) 과 하나의 중간 지점의 선분을 가진 경우

 

풀이에서는 2번과 3번의 경우를 다 따져보겟습니다.

2 번의 경우에는 한쪽 극단을 기준으로 나머지 극단을 이분탐색하여 오른쪽 끝과 왼쪽 끝이 가장 멀리 있으면서도 구간에 포함되게 찾으면 됩니다.

3 번의 경우에는 중앙 구간을 기준으로 왼쪽으로 이분탐색, 오른쪽으로 이분탐색 해주면 됩니다.

 

 

- 파이썬의 경우 bisect 라이브러리을 사용하시면 코드 량을 훨씬 줄일 수 있습니다.

 

 

정답코드 (Python, 파이썬)

import sys; input = sys.stdin.readline
n, l, r = map(int, input().split())
arr = [[],[],[]]
ans = int(1e10)
for _ in range(n):
    a,b = map(int, input().split())
    if a <= l and b >= r:
        print(0)
        exit()
    if b < l or a > r:
        continue
    if a <= l:
        arr[0].append(b)
    elif b >= r:
        arr[2].append(a)
    else:
        arr[1].append((a,b))
if not arr[0] or not arr[2]:
    print(-1)
    exit()
arr[0].sort()
arr[2].sort()

def bisect1(y):
    global ans
    st = 0
    fi = len(arr[2]) - 1
    res = 0
    while st <= fi:
        mid = (st + fi) // 2
        if arr[2][mid]> y:
            fi = mid - 1
        else:
            st = mid + 1
            res = arr[2][mid]
    if not res:
        return
    ans = min(ans, abs(y - res))
def bisect2(x,y):
    global ans
    st = 0
    fi = len(arr[0]) - 1
    res = 0
    tem = 0
    while st <= fi:
        mid = (st + fi) // 2
        if arr[0][mid] < x:
            st = mid + 1
        else:
            fi = mid - 1
            res = arr[0][mid]
    if not res:
        return
    tem += abs(res - x)
    st = 0
    fi = len(arr[2]) - 1
    res = 0
    while st <= fi:
        mid = (st + fi) // 2
        if arr[2][mid] > y:
            fi = mid - 1
        else:
            st = mid + 1
            res = arr[2][mid]
    if not res:
        return
    tem += abs(y - res)
    ans = min(ans, tem)

for x in arr[0]:
    bisect1(x)
for x,y in arr[1]:
    bisect2(x,y)
ans = -1 if ans == int(1e10) else ans
print(ans)

 

정답코드 (Rust, 러스트)

use std::{io, vec};
use std::io::prelude::*;

fn read<T>(si: &mut T) -> String where T: Read {
    let mut s = String::new();
    si.read_to_string(&mut s).unwrap();
    s
}

fn next<T>(it: &mut std::str::SplitAsciiWhitespace) -> T where
    T: std::str::FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug {
    it.next().unwrap().parse().unwrap()
}

fn bisect(arr: &Vec<(i64,i64)>, A_arr: &Vec<i64>, B_arr: &Vec<i64>, l: i64, r: i64) -> i64 {
    let mut st: i32 = 0;
    let mut fi:i32 = A_arr.len() as i32 - 1;
    let mut res = 0;
    let mut ans = 0;
    while st <= fi {
        let mid = (st+fi) >> 1;
        if A_arr[mid as usize] < l {
            st = mid + 1;
        } else {
            fi = mid - 1;
            res = A_arr[mid as usize] ;
        }
    }
    if res == 0  {
        return i64::MAX;
    }
    ans += i64::abs(res - l);
    res = 0;
    st = 0;
    fi = B_arr.len() as i32 - 1;
    while st <= fi {
        let mid = (st+fi) >> 1;
        if B_arr[mid as usize] > r {
            fi = mid - 1;
        } else {
            st = mid + 1;
            res = B_arr[mid as usize] ;
        }
    }
    if res == 0 {
        return i64::MAX;
    }
    ans += i64::abs(r - res);
    ans
}

fn bisect_mid(B_arr: &Vec<i64>, r: i64) -> i64 {
    let mut st: i32 = 0;
    let mut fi:i32 = B_arr.len() as i32 - 1;
    let mut res = 0;
    while st <= fi {
        let mid = (st+fi) >> 1;
        if B_arr[mid as usize] > r {
            fi = mid - 1;
        } else {
            st = mid + 1;
            res = B_arr[mid as usize] ;
        }
    }
    if res == 0 {
        return i64::MAX;
    }
    i64::abs(r - res)
}

fn main() {
    // 입력
    let mut si = io::BufReader::new(io::stdin().lock());
    let mut so = io::BufWriter::new(io::stdout().lock());
    let s = read(&mut si);
    let mut it = s.split_ascii_whitespace();

    let n = next::<i64>(&mut it);
    let l = next::<i64>(&mut it);
    let r = next::<i64>(&mut it);

    let mut ans = i64::MAX;
    let mut arr: Vec<(i64,i64)> = Vec::new();
    let mut A_arr = Vec::new();
    let mut B_arr = Vec::new();
    for _ in 0..n {
        let a = next::<i64>(&mut it);
        let b = next::<i64>(&mut it);
        if a <= l && b >= r {
            ans = 0;
        }
        if b < l || a > r {
            continue;
        }
        if a <= l {
            A_arr.push(b);
        } else if b >= r {
            B_arr.push(a);
        } else {
            arr.push((a, b));
        }
    }
    if ans == 0 {
        writeln!(so, "0").ok();
    } else {
        A_arr.sort_unstable();
        B_arr.sort_unstable();
        for i in 0..arr.len() {
            let (x,y) = arr[i];
            ans = ans.min(bisect(&arr,&A_arr,&B_arr,x, y));
        }
        for i in 0..A_arr.len() {
            let x = A_arr[i];
            ans = ans.min(bisect_mid(&B_arr, x));
        }
        if ans == i64::MAX {
            writeln!(so, "-1").ok();
        } else {
            writeln!(so, "{}", ans).ok();
        }
    }
}

 

 

문제 풀이 후 생각

- 문제를 보고 이분탐색은 떠올렷는데 어떻게 쓰는 거지? 라고 생각하신 분들과 이게 왜 이분탐색이지? 라고 생각하신 분들에게 도움이 되었으면 좋겟습니다.

 

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요