백준 9464: 직사각형 집합

이게 왜 solved.ac 골드 1에 있는 문제인지 의문스럽다.

 

문제의 제한 시간은 2초, 1,000,000보다 작거나 같은 모든 L에 대해 선분의 길이 쌍을 모두 구하고도 남을 시간이다.

(3, 4), (5, 12), (8, 15) ... 와 같은 쌍을 모두 준비하는 방법을 생각해보자.

 

첫번째 조건은 세 성분을 잘 조합했을 때 '피타고리안 트리플'이 되어야 한다는 것이다. 3, 4가 있다면 다른 한 수는 5가 되어야 한다는 것이다.

두번째 조건은 폭보다 높이가 커야한다는 것으로, (3, 4), (4, 3)에서는 (3, 4)만이 유효하다는 것을 알 수 있다.

마지막 조건은 두 수의 최대공약수가 1이어야 한다는 것, 다시 말해 두 수가 서로소여야 한다는 것이다. (3, 4)는 허용해도, (6, 8)은 안 된다는 것이다. 굳이 (6, 8)을 포함하고 (3, 4)를 포기하는 방법도 있지만 최대 직사각형의 수를 구하기 위해서는 항상 작은 것이 이득일 것이다.

 

결국 그렇게 구한 모든 쌍을 w성분과 h성분의 합으로 정렬한 다음, 그리디하게 앞에서부터 L에서 빼주면 된다.

 

EVAL_MAX가 10000L일 때,

    var a = 1L
    var b = 1L
    val list = ArrayList<Pair<Long, Long>>()
    var sum = 0L
    while (a + b <= EVAL_MAX) {
        val c = sqrt((a * a + b * b).toDouble()).toLong()
        if (c * c == a * a + b * b) {
            if (gcd(a, b) == 1L) {
                list.add(a to b)
                sum += (a + b) * 2
            }
        }

        b++
        if (b == EVAL_MAX - a) {
            a++
            b = a
        }
    }

    list.sortBy { it.first + it.second }

a, b 모두 1부터 전부 구해봤자 최종적으로 400ms 안팎의 시간밖에 소요되지 않는다는 점만 기억하면 쉽게 풀 수 있을 것이다.