백준 32625: 분할

🧭 문제 분석

N개의 정수로 이루어진 배열 A가 있다.
이 배열을 연속 구간으로 나눴을 때, 각 구간의 최솟값 + 최댓값의 크기가 모두 같아야 한다.
나뉘어진 구간의 길이는 모두 같다.

✅ 문제 풀이

N은 최대 10만이 가능하므로, N^2으로는 해결 불가한 문제다
그래서 단순한 이중 for문으로는 해결할 생각 하지말자

사실 문제의 조건에 답이 나와있다
구간을 나눌 때 모든 구간의 길이가 같아야 한다
모든 구간의 길이가 같으려면 N이 구간의 길이로 나누어 떨어져야 한다
즉, (N % 구간의 길이) == 0 이 되어야 할 것이다

위 조건을 충족하는 숫자는 N의 약수라고 할 수 있다
N의 약수를 가장 효율적으로 구하는 방법은 N의 제곱근까지 탐색하는 것이다

예를 들어서 N이 64라고 해보자
N의 약수는 1, 2, 4, 8, 16, 32, 64 인데,
N에 자기 자신을 나눈 수가 N의 제곱근을 기준으로 반대편에 배치되어 있다
(64를 2로 나누면 32고, 64의 제곱근인 8을 기준으로 반대편에 위치하고 있다)

그래서 N의 제곱근까지만 탐색하면 되는 것이다
어차피 N에 약수를 나누면 또 다른 약수를 얻을 수 있다

이제 구간을 나누고 탐색해보자

val N = readln().toInt()
val A = readln().split(" ").map(String::toInt)
// 구간의 길이가 1일 때도 확인해보기
if (A.sorted().run { first() == last() }) {
    print(1)
    return
}

// N의 제곱근까지 확인해보기
for (n in 2..sqrt(N.toDouble()).roundToInt()) {
   ...
}

구간의 길이 n은 N의 약수고, N/n도 N의 약수다
두 값으로 구간을 나누어 최소, 최댓값의 합을 확인해본다

...
for (n in 2..sqrt(N.toDouble()).roundToInt()) {
   // 약수면 확인
   if (N % n == 0) {
       loop@ for (chunkLength in listOf(n, N / n)) { // n, N/n 다 확인
            // 첫번째 구간의 최소+최대
            var prev = A.subList(0, chunkLength).run { minOf { it } + maxOf { it } }
            // 각 구간 탐색
            for (s in chunkLength until N step chunkLength) {
                // 최소, 최대 저장할 변수
                var (min, max) = Int.MAX_VALUE to Int.MIN_VALUE
                // 현재 구간의 최소, 최대 탐색 반복문
                for (j in s until s + chunkLength) {
                    min = minOf(min, A[j])
                    max = maxOf(max, A[j])
                }
                
                // 값 다르면 바로 루프 종료
                if (prev != max + min) continue@loop
                prev = max + min
            }
            
            // 모든 조건문 다 통과했으면 모든 구간의 최소+최대 계산값이 동일
            print(1)
            return
       }
   }
}

// return 못 되고 내려왔으면 불가능
print(0)

결과적으로 O(N의 제곱근) * O(N + N)이 소모되므로, 시간 제한을 통과할 수 있게 된다