• 백준 3053번 택시 기하학 :: 마이구미
    알고리즘 풀이/수학 2016. 10. 18. 20:28
    반응형

    이번 글은 백준 알고리즘 3053번 "택시 기하학" 을 다뤄본다.

    문제 이름 그대로 택시 기하학에 관한 문제이다.

    문제는 아래와 같다.


    19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다.

    택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다.

    D(T1,T2) = |x1-x2| + |y1-y2|

    두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다.

    따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다.

    원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합

    반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오.



    유클리드 기하학과 택시 기하학에 대해 알고 있다면 쉽게 풀 수 있는 문제이다.

    이론에 대해서는 크게 다루지 않겠다.....

    아래의 링크가 잘 이해하게 쓰여졌다.

    http://m.blog.naver.com/alwaysneoi/100172516753

    보기 싫으면 안 봐도 된다... 내가 푼 소스의 해석만으로도 이해할 수 있게 해보겠다.


    자, 그렇다면 이제 어떻게 문제를 풀 것이냐?

    문제에선 반지름이 주어진다.

    이 반지름을 통해 원의 넓이만 구하면 되는 것이다.


    위의 링크를 봤다면 유클리드 기하학은 원의 형태이고, 택시 기하학은 정사각형의 형태라는 것을 알 수 있다.

    즉, 유클리드 기하학은 원의 넓이 공식 파이 * (반지름)제곱이고, 택시 기하학은 정사각형이므로 한변의길이 * 한변의 길이이다.

    그렇다면 유클리드 기하학의 경우는 입력되는 반지름을 통해 풀면된다.

    문제는 택시 기하학의 경우이다.

    한변의 길이를 어떻게 구할 것인가?

    쉽게 첫단계를 생각해보면, 반지름이 주어진다.

     => 지름까지 구할 수 있다. => 지름은 대각선의 길이이다.

    정사각형의 대각선의 길이를 구하는 공식은 뭐더라??

    한변의 길이 * 2 가 공식이다.


    이 공식을 활용해보자. (r은 반지름 a는 한변의 길이)

    2r = √ 2 * a => 양쪽 제곱 처리 => 4r^2 = 2a^2 => 양쪽 2 나누기 => 2r^2 = a^2

    결과적으로  2r^2 = a^2 라는 식이 나온다.

    a^2은 정사각형의 넓이이다. 그렇다는 건 2r^2를 구한다면 택시 기하학의 원의 넓이가 나온다는 것이다.

    이해가 안간다면 펜을 들고 적으면서 해보자. 

    어려운 내용은 하나도 없다.

    아래 소스를 올려놓겠다.


    3034번 문제는 대각선 구하는 공식과 관련되어 풀 수 있는 문제이다.

    쉬운 문제이고 공식을 활용하고 기억하기 좋은 문제이니 한번 풀어보면 좋다.

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


    import java.io.IOException; import java.text.DecimalFormat; import java.util.Scanner; public class Main { public static void main(String[] args) throws IOException { //정사각형 대각선 길이 공식 한변길이 * 루트2 //택시 기하학 - 정사각형 //2r = 루트2 * 한변길이 //4*r제곱 = 2*a제곱 => 2*r제곱 = a제곱 (원의 넓이) DecimalFormat df = new DecimalFormat("0.000000"); Scanner sc = new Scanner(System.in); int r = sc.nextInt(); double pi = Math.PI; System.out.println(df.format(r*r*pi)); System.out.println(df.format(r*r*2)); } }





    반응형

    댓글 0

Designed by Tistory.