TIL: 2019년 6월 교육청 고2 수학 '가'형 30번 알고리즘 구현

문제 요약

주어진 조건을 만족하는 네 양의 정수 (a, b, c, d) 쌍의 개수가 정확히 59개가 되는 가장 작은 자연수 m과 가장 큰 자연수 M을 찾고, 그 합 M + m을 구하는 문제.

조건:

(a^(1/b)) * (c^(1/d)) = 24^(1/5)

수학적 접근

해당 문제는 수치 비교에서 실수 오차가 발생할 수 있기 때문에, 정확한 수 비교를 위해 로그를 이용한 비교로 전환했다.

변형 수식:

log(a^(1/b)) + log(c^(1/d)) = log(24^(1/5))
⇒ (1/b) * log(a) + (1/d) * log(c) = log(24)/5

이 식을 기반으로 실수 비교를 수행함.

구현 전략

1. k의 범위를 2부터 200까지 순차적으로 증가시키며 검사
2. a, b, c, d를 각각 [2, k], [1, k] 범위로 완전 탐색
3. 위 수식의 좌변이 log(24)/5와의 차가 epsilon보다 작을 경우 조건 만족으로 판단
4. 조건을 만족하는 쌍을 Set<String>에 저장해 중복 제거
5. count == 59일 때의 최소 k와 최대 k를 저장
6. 최종적으로 M + m 출력

핵심 코드

for (int k = 2; k <= 200; k++) {
    Set<String> seen = new HashSet<>();
    int count = 0;

    for (int a = 2; a <= k; a++) {
        for (int b = 1; b <= k; b++) {
            for (int c = 2; c <= k; c++) {
                for (int d = 1; d <= k; d++) {
                    double lhs = Math.log(a) / b + Math.log(c) / d;
                    if (Math.abs(lhs - target) < epsilon) {
                        seen.add(a + "," + b + "," + c + "," + d);
                        count++;
                    }
                }
            }
        }
    }

    if (count == 59) {
        if (minK == 0) minK = k;
        maxK = k;
    }
}

주요 고려 사항

• 부동소수점 오차 방지: Math.abs(lhs - target) < epsilon 조건 활용
• 중복 제거: (a,b,c,d) 쌍을 문자열로 구성하여 Set에 저장
• 정수 범위 제한: a, c는 2 이상부터 시작 (1이면 의미 없는 조합이 되므로)

결과

정확히 k = 72와 k = 80에서 59개의 조합이 존재함을 확인했고, 최종 결과는:

M + m = 152

배운 점

• 로그를 통한 수식 비교는 실수 오차 처리에 매우 유용하다
• 완전 탐색 알고리즘은 조건을 명확히 이해하고 효율적으로 구성하면 계산 가능한 수준에서 문제를 해결할 수 있다
• 수학적 사고력과 구현력이 결합되면 교과서 수준 문제도 코드로 정복 가능하다