Problem 9 : Special Pythagorean triplet (5%)

link

Description

original

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

$a^2 + b^2 = c^2$ 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.

간략해석

피타고라스 쌍 중에 세변 길이를 a,b,c라 할때, 합이 1000인 쌍들의 abc합을 구하여라.

Idea & Algorithm

naive idea

피타고라스 세쌍을 구하는 방법은 여러가지가 있지만 범위가 작기때문에 단순 반복문을 돌려도 된다.

하지만 3중 포문은 비효율적이고 세변의 합이 1000임을 이용해 a,b를 결정하면 c가 자동적으로 결정된다.

따라서 $O(N^2)$으로 해결가능하다. 여기서 N은 범위다.

advanced idea

source code

#include <stdio.h>

int main(){
    for(int i = 1 ; i < 1000 ; i++){
        for(int j = i ; j < 1000 ; j++ ){
            int tmp = 1000 - i - j;
            if(i*i + j *j == tmp*tmp){
                printf("%d",i*j*tmp);
            }
        }
    }
}

Problem 009