백준 14583번 이음줄 :: 마이구미

이번 글은 백준 알고리즘 문제 14583번 "이음줄" 을 다뤄본다.

최근 고려대학교 프로그래밍 대회에서 출제된 문제이다.

본인은 굉장히 신선한 문제라고 생각했다.

문제 풀이는 직사각형, 평행사변형, 피타고라스, 각의 이등분선 등에 대한 이론이 필요하다.

학생시절 머리 좀 써야하는 수학문제를 푼다는 느낌을 받을거라 생각한다.

문제는 링크를 통해 확인하길 바란다.

직사각형 종이를 접힌 부분을 표시해보면 아래와 같다.

우리가 구해야할 것은 보라색 영역의 가로와 세로가 된다.

우리는 직사각형의 대각선의 길이인 d를 먼저 구할 수 있다.

h, v 가 주어진 상태이기 때문에 △ABC를 피타고라스의 정리를 이용할 수 있다.

double d = Math.sqrt(h * h + v * v);

  

그 다음, 각의 이등분선의 성질을 이용해야한다. (각의 이등분선의 성질)

△ABE와 △ABC가 닮음이 되기 때문에, 아래와 같은 길이의 비를 나타낼 수 있다.

a : b = h : d

=> code 
double a = v * (h / (h + d));
double b = v * (d / (h + d));

이제는 △ABE의 빗변인 c를 피타고라스의 정리를 통해 구할 수 있게 되었다.

double c = Math.sqrt(a * a + h * h);

구해야할 직사각형의 가로 길이는 c를 통해 얻을 수 있다.

반반 접었기 때문에 2를 나누어주면 된다.

System.out.format("%.2f", c / 2);

세로의 길이(k)는 평행사변형의 높이가 된다.

k를 구하기 위해서 △ABE △CDF를 보자.

두 삼각형은 같은 삼각형이라는 것을 알 수 있다.

평행사변형의 넓이는 큰 직사각형에서 두 삼각형을 뺀 넓이와 같다.

△CDF 를 위로 올린 후 직사각형을 보면 아래와 같다.

점선으로 표시된 직사각형과 평행사변형이 같은 넓이를 가진다는 것을 알 수 있다.

평행사변형의 높이 공식을 통해 k를 구할 수 있게 된다.

평행사변형의 높이 = 평행사변형의 넓이 / 밑변
System.out.format("%.2f", (b * h) / c);

전체 소스는 아래 Github URL을 통해 확인하길 바란다.

백준 알고리즘 14583번 "이음줄" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/math/14583.java