[Java] 백준 풀기 1711 - 직각삼각형

자바 백준 1711번

골드 5

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

1711번: 직각삼각형

 

 

 

 

 

문제 보기

분류: 브루트포스 알고리즘, 기하학, 피타고라스 정리

 

 

 

 

 

문제 풀기

이 문제는 그다지 좋아하지 않는 시간초과 해결이 관건이기에 별로인 문제이다. Scanner를 사용하여 제출해 보진 않았지만 분명 시간초과 걸렸을 것이다. 이를 피하기 위해 BufferedReader를 사용한다.

 

BufferedReader를 이용하여 주어진 모든 좌표를 long 타입으로 입력받고, 브루트포스 알고리즘답게 모든 경우의 수를 생각하여 점 3개씩 꺼내어 만들 수 있는 세 변의 길이를 모두 구하여 피타고라스 정리를 만족하는지 확인한다. 만족할 때마다 누적 카운트 하여 출력한다.

 

 

 

 

 

코드 보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 좌표를 나타내는 Point 클래스 정의
class Point {
    long x, y;
    
    public Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력을 위한 BufferedReader 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 점의 개수 N을 입력 받음
        int N = Integer.parseInt(br.readLine());
        
        // 입력된 좌표를 저장할 Point 배열 선언
        Point[] points = new Point[N];
        for (int i = 0; i < N; i++) {
            // 각 점의 x, y 좌표를 공백으로 구분하여 입력 받고 Point 객체로 저장
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            points[i] = new Point(x, y);
        }
            
        // 직각삼각형 개수를 세기 위한 변수 초기화
        long count = 0;
        
        // 세 개의 점을 선택하여 직각삼각형인지 확인하는 루프
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                for (int k = j + 1; k < N; k++) {
                    long x1 = points[i].x;
                    long y1 = points[i].y;
                    long x2 = points[j].x;
                    long y2 = points[j].y;
                    long x3 = points[k].x;
                    long y3 = points[k].y;
                    
                    // 세 점 사이의 거리 계산
                    long dist1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                    long dist2 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
                    long dist3 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
                    
                    // 피타고라스 정리를 사용하여 직각삼각형인지 확인
                    if (dist1 + dist2 == dist3 || dist1 + dist3 == dist2 || dist2 + dist3 == dist1) {
                        count++;
                    }
                }
            }
        }
        
        // 결과 출력
        System.out.println(count);
    }
}