009. Special Pythagorean Triplet (합이 k가 되는 피타코라스 수 구하기)

​문제 (English)

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 Pythangorean triplet for which $a+b+c=1000$

Find the product $abc$.

 

Answer: 31875000

문제 분석

---

피타고라스 정리를 만족하는 수 a,b,c에 대해, a+b+c=1000이 될 때의 abc를 구하는 문제이다.

 

Euler Proejct에서는 a+b+c=1000이 되는 abc를 구하는 문제 하나이고, hackerranker에서는 a+b+c=N이 되는 abc를 구하는 문제로 확장.

 

풀이 1 

---

가장 간단히 생각해 볼 수 있는 풀이 방법이다.

1) S=a+b+c

2) a를 S에서 시작해서 점점 작은 수로 감소 시키면서 루프1

3) b=a+1에서 S까지 증가시키면서 루프2

4) c = S - (a+b)

5) 만약 c <= b이면 break 루프2

6) $a^2+b^2=c^2$을 만족하면, 답 p=abc이고 루프1을 벗어남

 

핵심은 a를 큰 수에서 작은 수로 감소시키면서 경우의 수를 찾는 것. 이래야 $a+b+c=S$와 $a^2+b^2=c^2$을 만족시키는 첫 번째 값이 가장 큰 값이 된다. (S가 같으면서 다른 {a,b,c}쌍이 있다. 예를 들어 S=90을 만족하는 피타고라스 수는 {9,40,41}과 {15,36,39}

 

위 알고리즘 5)에서 c<=b이면 더 이상 b를 증가시킬 필요 없다. 

예를 들어 S=30의 경우, a=10에 대해서 b=11부터 출발. 이때 c=30-(11+10)=9. 따라서 c가 b보다 작기에 조건 a<b<c를 만족하지 못함.

이 경우 b=12로 증가시켜도 c=30-(12+10)=8이되어, 점점 c가 작아지는 방향이기에, 이 경우 b를 더 증가시키면서 c를 찾아봐야 무의미하기에, 루프2를 벗어나는 것임

 

코드는,

#[test]
fn test(){    
    assert_eq!(-1, answer(2));
    assert_eq!(-1, answer(3));
    assert_eq!(-1, answer(4));
    assert_eq!(-1, answer(5));
    assert_eq!(60, answer(12)); //3,4,5   

    assert_eq!(480, answer(24));
    assert_eq!(780, answer(30));
    assert_eq!(4200, answer(56));
    assert_eq!(21060, answer(90));
    assert_eq!(1620, answer(36));
    assert_eq!(12180, answer(70));

    assert_eq!(31875000, answer(1000));  
}

#[cfg(test)]
fn answer(s: i32) -> i64{
    let mut max_product: i64 = -1;          
    'outer: for a in (3..s).rev(){        
        for b in (a+1)..s{
            let c: i32 = s - (a+b);
            if c <= b {
                break;
            }
            if c*c == a*a + b*b {                
                max_product = a as i64 * b as i64 * c as i64;
                break 'outer;
            }
        }
    }
    return max_product;
}

 

이 풀이 방법은 충분히 빠르다. hackerrank 사이트를 통과한다.

 

풀이 2 

---

풀이1도 빠르지만, a와 b의 범위를 줄여서, 연산량을 줄일 수 있다. 

 

조건식을 다시 보면,

• $a+b+c=s$  (식1)
• $a^2+b^2=c^2$ (식2)
• $a<b<c$  (식3)

a가 가질 수 있는 최댓값을 s를 이용해서 표현해 보자.

 

(식1)과 (식3)에서, a가 최댓값을 가진다는 것은 b와 c가 a 대비 최솟값이라야 하고, 이 경우는 {a, a+1, a+2}의 경우이다.

(식1)에 이 값을 대입해 보면, $a+(a+1)+(a+2)=3a+3=s$ 

따라서 $a=(s-3)/3$이 a가 가질 수 있는 최댓값이다.

 

이제 b가 가질 수 있는 최댓값을 s와 a로 나타내보자.

(식 3)에서 $b<c$이고, (식 1)에서 $c=s-a-b$이다. 따라서, $b<s-a-b$이고 $2b<s-a$가 되어 $b<(s-a)/2$가 된다. 

1) a의 범위: 3에서 (s-3)/3

2) b의 범위: (a+1)에서 (s-a)/2

 

위 a, b 범위로 루프를 돌리면 된다.

 

fn answer1(s: i32) -> i64{
    let mut max_product: i64 = -1;     
    let a_limit:i32 = (s-3) / 3;      
    'outer: for a in (3..=a_limit).rev(){
        let b_limit: i32 = (s-a) / 2;        
        for b in (a+1)..=b_limit{
            let c: i32 = s - (a+b);
            if c <= b { break;}
            if c*c == a*a + b*b {                
                max_product = a as i64 * b as i64 * c as i64;
                break 'outer;
            }
        }
    }
    return max_product;
}

 

총평

---

a < b < c 및 a+b+c=s의 조건에 맞게, 최소한의 a, b를 선택해서 $a^2+b^2=c^2$을 만족하는 수를 찾아내는 것이 알고리즘의 핵심이다.

또한, a를 큰 수에서 작은 수로 감소시키면서 루프를 돌게 해야, $a^2+b^2=c^2$를 만족하는 첫 번째 수가 가장 큰 값이 된다. 그렇지 않으면, 구한 $p=abc$값이 최댓값인지를 모든 루프를 돌면서 체크해야 한다. 

 

전체 소스코드

---

p9.rs 

#[test]
fn test(){    
    assert_eq!(-1, answer(2));
    assert_eq!(-1, answer(3));
    assert_eq!(-1, answer(4));
    assert_eq!(-1, answer(5));
    assert_eq!(60, answer(12)); //3,4,5   

    assert_eq!(480, answer(24));
    assert_eq!(780, answer(30));
    assert_eq!(4200, answer(56));
    assert_eq!(21060, answer(90));
    assert_eq!(1620, answer(36));
    assert_eq!(12180, answer(70));

    assert_eq!(31875000, answer(1000));  
}

#[cfg(test)]
fn answer(s: i32) -> i64{
    let mut max_product: i64 = -1;          
    'outer: for a in (3..s).rev(){        
        for b in (a+1)..s{
            let c: i32 = s - (a+b);
            if c <= b {
                break;
            }
            if c*c == a*a + b*b {                
                max_product = a as i64 * b as i64 * c as i64;
                break 'outer;
            }
        }
    }
    return max_product;
}


//------------------
#[test]
fn test1(){    
    assert_eq!(-1, answer1(2));
    assert_eq!(-1, answer1(3));
    assert_eq!(-1, answer1(4));
    assert_eq!(-1, answer1(5));
    assert_eq!(60, answer1(12)); //3,4,5   

    assert_eq!(480, answer1(24));
    assert_eq!(780, answer1(30));
    assert_eq!(4200, answer1(56));
    assert_eq!(21060, answer1(90));
    assert_eq!(1620, answer1(36));
    assert_eq!(12180, answer1(70));

    assert_eq!(31875000, answer1(1000));  
}

#[cfg(test)]
fn answer1(s: i32) -> i64{
    let mut max_product: i64 = -1;     
    let a_limit:i32 = (s-3) / 3;      
    'outer: for a in (3..=a_limit).rev(){
        let b_limit: i32 = (s-a) / 2;        
        for b in (a+1)..=b_limit{
            let c: i32 = s - (a+b);
            if c <= b { break;}
            if c*c == a*a + b*b {                
                max_product = a as i64 * b as i64 * c as i64;
                break 'outer;
            }
        }
    }
    return max_product;
}

 

끝