Joonas' Note

Joonas' Note

BOJ 2022 - 사다리 본문

알고리즘/문제 풀이

BOJ 2022 - 사다리

2018. 2. 8. 21:07 joonas

    [이전 블로그에서 글 옮김]


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

    https://uva.onlinejudge.org/...&problem=1507



    \(a, b, c\) 가 주어지면 \(k\) 를 구해내는 문제이다.


    피타고라스로 A, B를 구해서 기울기를 구하고, 두 직선의 교점 방정식을 이용했다. 그리고 교점의 y 위치가 \(c\) 가 되는 순간을 구하도록 이분 탐색을 했다.


    우선 a가 포함된 직선을 g(x), b가 포함된 직선을 f(x)라 한다면 아래와 같은 정보가 나온다.


    \(
    \begin{cases}
    A = \sqrt{a^2 - k^2} \\
    B = \sqrt{b^2 - k^2}
    \end{cases}
    \)


    \(
    \begin{cases}
    f(x) = \frac{B}{k}x \\
    g(x) = -\frac{A}{k}x+A
    \end{cases}
    \)


    두 직선이 만나는 순간을 \( (c_0, c) \)라 한다면 \( f(c_0) = g(c_0) = c \) 이여야 한다.


    \(
    \begin{align}
    f(c_0) = & \frac{B}{k}c_0 = c \\
    & c_0 = \frac{k \cdot c}{B}
    \end{align}
    \)


    \(g(c_0) = g(\frac{k \cdot c}{B}) = c\) 가 나온다면 정답일것이다.


    \(k\)를 찾는 과정에서 \(f(c_0) \gt c\) 라면 높이가 더 높은 좌표이므로 \(c_0\)을 줄여야한다는 뜻이다. \(k\)를 줄이면 \(c_0\)도 줄어든다.


    \(k\)를 조정해서 만들어진 적당한 \(x\)로 \(f(x) = g(x)\)가 성립하는 지 확인하면서, 결과에 따라 \(k\)를 다시 조정하면 정답이 나온다.


    \(k\)를 찾는 구간을 줄일 때 epsilon을 1e-5로 설정했을 때는 오답이었다. 이분탐색이 중간에 잘못되고 있나 생각에 구글링하다가 더 작은 결과까지 해보도록 1e-9 로 바꿨더니 정답을 맞았다. 너무 허무함


    '알고리즘 > 문제 풀이' 카테고리의 다른 글

    BOJ 15685 - 드래곤 커브  (0) 2018.04.17
    BOJ 12755 - 수면 장애  (0) 2018.04.17
    알고리즘 공부 순서  (0) 2017.12.08
    BOJ 2887 - 행성 터널  (0) 2017.11.03
    BOJ 2718 - 타일 채우기  (0) 2017.11.03
    Comments