Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 4월 8일 일요일

[Project Euler] 39. 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?

39. 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?

세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다.

{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
1000 이하의 둘레 p에 대해서, 직각삼각형이 가장 많이 만들어지는 p의 값은 얼마입니까?
Click

9번문제을 좀더 일반화 한 문제네요.
a + b + c = n 에서.
b + c = n - a
b = (n - a) - c
n-a -> t로 놓으면... -> b = t - c
피타고라스 정리에 넣으면..

a ² + b ² = c ² 는
a ² + (t-c) ² = c²
a ² + t ² - 2*t + c ² = c²
a ² + t ² = 2*t*c
( a ² + t ² ) / (2*t) = c

여기서 t = n-a 이므로... 주어진 n에서 a만 알면, c와 b를 구할 수 있다.

여기에 9번에서 미쳐 생각못한 부분인... 조건문의 범위를 a < n까지가 아닌 a < b까지로 그리고 문제에 맞게 약간의 수정을 통해 완료했습니다.
<script language="Javascript" type="text/javascript">
function p039(n){
    var r=0, max = 0;
    for(var i=1; i<=n; i++){
        var a, b=i, c;
        var cnt = 0;
        for(a=1; a < b; a++){
            var t = i-a;
            c = parseInt((a*a + t*t) / (2*t));
            b = i - a - c;
            
            if(a*a + b*b == c*c && b!=0)
                cnt ++;
        }
        if(cnt > max){
            max = cnt;
            r = i;
        }
    }
    
    return r;
}
</script>

댓글 4개:

  1. 제 소스보다 훨씬 간단하군요 :)
    이것을 유도하는 과정도 훨씬 간단하고 ㅎㅎ

    그런데 혹시
    i = 1이고 a = 1이면 t = 0이 되는데
    c값이 제대로 들어가지나요~?

    답글삭제
    답글
    1. 아시겠지만 i가 변의 총 길이이고 a가 그 중 한 변의 길이이니 둘이 같으면 삼각형을 만들수가 없습니다.
      그래서 for문을 돌때도 해당 경우는 탐색하지 않도록... 처음 9번 풀때는 범위를 a < i 까지 탐색을 했었는데 요번에 약간 수정을해 a < b로 바꾸고 b의 초기 값을 i로 주어서 해당 경우는 탐색을 하지 않도록 하였습니다. ^^

      삭제
  2. 아.. 제가 "b = i"랑 "a < b"를 못봤네요
    그 부분은 잘 알겠습니다 :)

    그리고 이건
    크게 중요한 문제는 아닌 것 같긴 하지만
    위의 입력창에 60 미만의 수를 입력하고 클릭하면 답이 2로 나오네요 ^^;

    답글삭제
    답글
    1. 그렇군요... a=1, b=0, c=1 로 인식이 되나보네요.
      b가 0이 되는 것을 판단해줬어야 하네요. 미쳐 생각 못했는데.. 감사합니다. ^^

      삭제