[CUPOJ] 직각 삼각형 둘레 매 거 최적화 문제 풀이

직각 삼각형 의 둘레
제목 링크:https://www.cupacm.com/newsubmitpage.php?id=1094 이것 은 매우 전형 적 인 매 거 진 문제 로 다음 과 같이 매 거 진 을 어떻게 최적화 하 는 지 한 걸음 한 걸음 분석 할 것 이다.
제목 설명
직각 삼각형 의 둘레 가 120 이면 세 변 은 20, 48, 52 또는 24, 45, 51, 그리고 30, 40, 50, 3 가지 다른 해 가 있 을 수 있다.지금 당신 은 직각 삼각형 의 둘레 를 정 하면 이 둘레 는 최대 얼마나 풀 수 있 는 지 알 고 싶 습 니까?변 의 길 이 를 정수 로 가정 하 다.
입력
첫 번 째 줄 의 T T T 는 T T 팀 의 테스트 데 이 터 를 나타 낸다.1 ≤ T ≤ 10000 1 \ \ leq T \ \ leq 10000 1 ≤ T ≤ 10000 각 조 의 테스트 데이터 가 한 줄 에서 차지 하 는 정수 A A A 만 포함.0 ≤ A ≤ 100000 0\leq A\leq 100000 0≤A≤100000
출력
각 조 의 테스트 데이터 에 따라 정수 A 를 둘레 로 하 는 직각 삼각형 의 개 수 를 요청 합 니 다.(변 의 길 이 는 모두 정수 인 직각 삼각형 이 고 둘레 는 정수 A)
샘플 입력

2
12
120

샘플 출력

1
3

해제
이것 은 매우 전형 적 인 매 거 진 문제 입 니 다. 다음은 매 거 진 을 어떻게 최적화 하 는 지 한 걸음 한 걸음 분석 하고 다른 매 거 진 문제 에 대해 시사 점 을 주 기 를 바 랍 니 다.
0. 삼중 순환
이 문 제 를 보면 먼저 세 개의 변 을 매 거 하고 세 개의 변 을 합치 면 둘레 와 같 고 피타 고 라 스 의 정리 에 부합 하면 조건 을 만족 시 키 고 계산 할 수 있다.

//TLE
ans = 0;
cin >> l;
for (int i = 1; i < l; i++) {
    for (int j = 1; j < l; j++) {
        for (int k = 1; k < l; k++) {
            if (i + j + k == l && i * i + j * j == k * k) {
                ans++;
            }
        }
    }
}
cout << ans / 2 << '
';

이렇게 가장 일반적인 매 거 시간 이 제한 을 초과 한 것 은 의심의 여지 가 없다.
1. 이중 순환
지금 은 최적화 시 켜 i ≤ j i \ \ leq j i ≤ j 를 지정 하면 i i 와 j j j 가 반복 적 으로 매 거 진 (예 를 들 어 345, 435 는 같은 답) 을 피하 고 시간 을 절약 할 수 있 습 니 다. k k k 는 경사 로 서 i j ij 와 둘레 를 통 해 k k k k 를 계산 하여 순환 을 줄 일 수 있 습 니 다.

//TLE
ans = 0;
cin >> l;
for (int i = 1; i < l; i++) {
    for (int j = i; j < l; j++) {
        int k = l - i - j;
        if (i * i + j * j == k * k) {
            ans++;
        }
    }
}
cout << ans << '
';

그래도 TLE.
2. 이중 순환 재 최적화
우선, 우 리 는 먼저 문제 에 대해 수학 분석 을 진행 합 니 다. 이미 알 고 있 는 i + j + k = l i + j + k = l, 0 < i ≤ j < k 0 < i \ leq j < k 0 < i ≤ j < k, 부등식 을 통 해 i < l / 3 i < l / 3 i < l / 3, j < l / 2 j < l / 2 j < l / 2 j < l / 2 j < l / 2.이중 순환 을 바탕 으로 i i 와 j j j 의 범 위 를 제한 합 니 다.

//716ms
ans = 0;
cin >> l;
for (int i = 1; i < l / 3; i++) {
    for (int j = i; j < l / 2; j++) {
        int k = l - i - j;
        if (i * i + j * j == k * k) {
            ans++;
        }
    }
}
cout << ans << '
';

이 제 는 이 문 제 를 통과 할 수 있어 700 여 밀리초 로 최적화 됐다.양쪽 의 합 이 세 번 째 변 보다 큰 성질 을 잡 으 려 면 600 밀리초 의 시간 이 필요 하 다.

//598ms
ans = 0;
cin >> l;
for (int i = 1; i < l / 3; i++) {
    for (int j = i; j < l / 2; j++) {
        int k = l - i - j;
        if (k < i + j && i * i + j * j == k * k) {
            ans++;
        }
    }
}
cout << ans << '
';

그럼 더 최적화 할 수 있 을까요?
3. 반복
우 리 는 다시 수학 으로 돌아 갈 수 있 습 니 다. 2 개의 방정식, 2 개의 미지수, 우 리 는 j j j 가 i i, l l 에 관 한 표현 식 을 쉽게 구 할 수 있 습 니 다.i + k + j = l i + k + j = l i + k + j = l, i 2 + j 2 = k 2 i ^ {2} + j ^ {2} = k ^ {2} i2 + j2 = k2, j = l - l 2 / (2 l - 2 i) j = l - l ^ {2} / (2l - 2i) j = l - l2 / (2l - 2i) j = l - l2 / (2l - 2i) 를 풀 수 있 습 니 다.수학 방법 을 통 해 우 리 는 j 의 표현 식 을 얻 었 고 j 가 l 보다 적 고 j 가 정수 라 고 판단 하면 된다.이러한 프로그램 은 한 번 의 순환 만 있 을 뿐이다. 우 리 는 프로그램 을 처음에 시간 초과 에서 1ms 로 최적화 시 켰 다. 이것 은 흔히 볼 수 있 는 최적화 방법 인 수학 방법 을 이용 하여 순환 횟수 를 줄 이 는 것 이다.

//1ms
ans = 0;
cin >> l;
for (int i = 1; i < l / 3; i++) {
    double j = l - (double) l * l / (2 * l - 2 * i);
    if (i < j && j - (int) j < 1e-5) {
        ans++;
    }
}
cout << ans << '
';

총결산
빈 거 를 통 해 한 문제 의 모든 가능성 을 옮 겨 다 니 며 조건 에 맞 는 가능성 을 찾 는 것 이 답 이다.매 거 할 때 수학 방법 을 사용 하여 문 제 를 최적화 시 켜 매 거 진 횟수 를 효과적으로 줄 이 고 알고리즘 의 효율 을 높 일 수 있다.