프로젝트 오일러 문제 - Problem 9

프로젝트 오일러 문제 - Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

피타고라스의 정리로 유명한 공식. 직각 삼각형의 빗변의 길이의 제곱은 나머지 다른 두 빗변의 길이의 제곱의 합과 같다.

각 변의 길이를 a, b, c라 할 때 피타고라스의 식을 만족하면서 a + b + c = 1000 이 되는 단 하나의 해가 있단다.

그것을 찾는 문제.

sol)

a<b<c 이므로 (=c가 가장 큰 값이므로) c를 1순위로 고정시키고 반복문 돌리고, 다음으로 b를 2순위로 고정시키고 반복문 돌리고, 마지막으로 a를 3순위로 고정시키고 반복문 돌린다. a가 반복되는 반복문 안에 조건문을 삽입하여 a+b+c == 1000 인지와, 이 세 수가 피타고라스의 정리를 만족하는지를 검사하면 된다.

소스 코드는 아래에.

package archives;

public class ProjectEuler9 {
	
	/*
	 	A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

				a2 + b2 = c2
				For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
				
		There exists exactly one Pythagorean triplet for which a + b + c = 1000.
		Find the product abc.
	 */
	
	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		int a=1000, b=1000, c=1001;
		
		while(c>0) {
			c-=2;
			for(b=c-1; b>0; b--) {
				for(a=b-1; a>=0; a-=2) {
					if( (a*a + b*b) == c*c) {
						if( (a+b+c) == 1000) {
							System.out.println("a="+a+" b="+b+" c="+c);
							System.out.println(a*b*c);
							break;
						}
					}
				}
			}
		}
		
		long end = System.currentTimeMillis();
		
		System.out.println("수행시간=" + (end-start) + " milisecond");
		
	}

}

c의 초기값이 1001(홀수) 인점과 c와 a의 값을 2씩 감소시킨 이유는 a 또는 b가 하나는 홀수, 다른 하나는 짝수가 되기 때문이다.

그리고 빗변의 길이 c 도 홀수이다.

예외로 a= '3의배수' / b= '4의 배수' / c= '5의 배수' 인 경우에는 c의 값이 짝수가 될 수는 있으나 a+b+c=1000을 만족하는 3:4:5의 수들은 없다.