728x90
[Gold V] 리벤지 오브 피타고라스 - 4563
성능 요약
메모리: 12928 KB, 시간: 248 ms
분류
수학(math), 정수론(number_theory)
문제 설명
피타고라스의 정리는 직각삼각형의 세 변의 관계를 나타내는 정리이다. 빗변의 길이를 C, 다른 두 변의 길이를 A, B라고 한다면 다음과 같은 식으로 쓸 수 있다.
A2 + B2 = C2
세 변의 길이가 모두 자연수인 직각삼각형 중에 가장 유명한 삼각형은 아래와 같다.
A = 12인 경우에는 다음과 같이 두 개의 직사각형을 찾을 수 있다.
A가 주어졌을 때, 빗변의 길이 C가 자연수인 직각삼각형을 만드는 자연수 B (B > A)는 몇 개가 있을까?
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 자연수 A (2 ≤ A < 220)이 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.
출력
입력으로 주어진 A에 대해서, 빗변의 길이가 자연수인 직각삼각형을 만드는 B(B>A)의 개수를 출력한다.
피타고라스의 성질을 활용하는 문제이다.
피타고라스의 공식을 활용하면
$$a^{2}+b^{2}=c^{2}$$
$$a^{2}=c^{2} -b^{2}$$
$$a^{2}=(c-b)(c+b) $$
가 된다.
즉 a제곱의 약수 중 곱해서 a제곱이 되는 두 수는 b와 c의 합과 차가 된다.
그 중 c-b가 a보다 크고, 합과 차의 합이 짝수가 되는 수를 찾으면 된다. (b와 c가 자연수가 되어야 함)
package Gold.g5;
import java.util.Scanner;
public class BOJ_4563_리벤지오브피타고라스 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int A = 0;
int cnt = 0;
while (true) {
A = sc.nextInt();
if (A == 0)
break;
// 삼각형이 될 조건
// c < a+b
// c^2 = a^2 + b^2;
// a2 = (b+c)(c-b)
long A2 = (long) Math.pow(A, 2);
// A의 약수 찾기
for (long i = 1; i <= A; i++) {
if (A2 % i == 0) {
long sub = i;
long sum = A2 / i;
if ((sum - sub) / 2 > A && (sub - sum) % 2 == 0) {
cnt++;
}
}
}
System.out.println(cnt);
cnt = 0;
}
}
}
728x90
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 1300 - K번째 수 (자바/Java) (0) | 2022.09.07 |
---|---|
[백준] 14888 - 연산자 끼워넣기 (자바/Java) (1) | 2022.09.05 |
[백준] 2580 - 스도쿠 (자바/Java) (0) | 2022.08.30 |
[백준] 9663 - N-Queen (자바/Java) (0) | 2022.08.26 |
[백준] 1676 - 팩토리얼 0의 개수 (자바/Java) (0) | 2022.08.26 |