[Kotlin, G5] 백준 1711번 직각삼각형

출처: unsplash.com

 

직각삼각형(1711번)

Gold 5

#브루트포스 알고리즘 #기하학 #피타고라스 정리

 

문제 내용

 

 

문제 접근

각 주어지는 점에서 무작위로 중복되지 않게 3개를 골라 만들 수 있는 직각삼각형의 개수를 구해야 한다.

점의 개수가 1500개까지 있고, 시간제한이 5초이다.

결정적으로 브루트포스 알고리즘으로 분류되어 있다.

이는 최대 1500개의 점에서 3개를 골라야 할 때, 무지성 탐색이 가능하다는 뜻이다.

 

무지성 탐색에서 나온 3개의 점에서 각 점 사이의 길이를 구하고 그 길이를 피타고라스 정리 공식을 이용해 직각삼각형인지 파악하면 된다.

두 점 (x1, y1), (x2, y2)가 있을 때, 두 점사이의 거리는

(x2 - x1) * (x2 - x1)의 제곱 + (y2 - y1) * (y2 - y1)의 제곱에 루트를 씌운 값이 된다.

 

두 점 사이의 거리를 이용해 피타고라스의 정리를 이용해 주면 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cnt = readLine().toInt()
    val points = mutableListOf<List<Int>>()
    var triangles = 0

    for (i in 0 until cnt) {
        points.add(readLine().split(" ").map { it.toInt() })
    }

    for (i in 0 until points.size) {
        for (j in i + 1 until points.size) {
            for (k in j + 1 until points.size) {
                val distance1 = getPointDistance(points[i][0], points[i][1], points[j][0], points[j][1])
                val distance2 = getPointDistance(points[j][0], points[j][1], points[k][0], points[k][1])
                val distance3 = getPointDistance(points[k][0], points[k][1], points[i][0], points[i][1])

                if (distance1 == distance2 + distance3 || distance2 == distance1 + distance3 || distance3 == distance1 + distance2) {
                    triangles++
                }
            }
        }
    }

    println(triangles)
}

private fun getPointDistance(x1: Int, y1: Int, x2: Int, y2: Int): Long {
    val distanceX = ((x2 - x1).toLong() * (x2 - x1).toLong())
    val distanceY = ((y2 - y1).toLong() * (y2 - y1).toLong())
    return distanceX + distanceY
}

 

문제 풀이

점들의 좌표를 입력받아서 들어간 좌표들 중 3개를 중복 없이 선택할 수 있게 3중 for문을 사용해 주고, 선택된 3개의 점을 이용해

각 점의 거리 3개를 구한 다음, 피타고라스 정리를 대입해서 직각삼각형의 개수를 세준다.

 

피타고라스 공식이, 가장 긴 변의 길이의 제곱이 나머지 변의 길이의 제곱이다.두 점의 거리 공식에서는 마지막에 루트를 씌워줘야 한다.루트를 씌우게 되면 소수가 되기 때문에 계산이 번거로워지고 미세한 수의 차이로 오답이 날 수 있기 때문에두 점 사이의 길이는 루트를 제거한 상태로 long 데이터로 변경해서 반환한다.

 

그러면 제곱한 데이터가 오기 때문에 피타고라스 정리 공식을 이용할 때 제곱을 할 필요 없이 덧셈만 진행해서 확인하면 된다.그러면 정확하게 값을 구할 수 있다.

 

 

문제 해결 과정

이거도 크게 어렵지 않다.

무지성 탐색으로 점 3개를 구할 수 있는 것이 편했던 것 같다.

전체 탐색으로 구한 3개의 점으로 피타고라스 정리를 활용하면 되는 문제이다.

내 기준 체감 난이도는 실버 4~실버 3이다.