[Silver I] 분할 - 32625

문제 링크

성능 요약

메모리: 126692 KB, 시간: 144 ms

분류

브루트포스 알고리즘, 집합과 맵

제출 일자

2026년 3월 4일 21:25:12

문제 설명

크기 $N$의 정수 배열 $A$가 있다. 다음 조건을 만족하도록 배열을 연속 구간으로 분할하는 것이 가능한지 판단하시오.

• 배열의 모든 원소가 정확히 하나의 구간에 포함된다.
• 각 구간의 크기는 $1$ 이상 $N$ 미만이며, 모든 구간의 크기는 같다.
• 각 구간에서 최솟값과 최댓값을 더한 값이 모든 구간에서 같다.

입력

첫째 줄에 배열의 크기 $N$이 주어진다. $(2\leq N \leq 100\,000)$

둘째 줄에 $A$의 원소 $A_{1}, A_{2}, A_{3}, \cdots, A_{N}$이 공백으로 구분되어 주어진다. $(1\leq A_{i} \leq N)$

출력

조건을 만족하도록 배열을 분할하는 것이 가능하다면 $1$을, 그렇지 않다면 $0$을 첫째 줄에 출력한다.

---

💡 해결 방법

💻 코드

 
 
n = int(input())
a = list(map(int, input().split()))
 
 
#크기 1에서 N-1 // 2 까지 분할해보며 구간 검색을 하면? > (N / 2) ^ 2 > 5000000000 50억인디 ;
#일단 해보자
 
for i in range(1, (n) // 2 + 1):
    if n % i == 0:
        ans = sum(
            (
                min(a[0*i :0 * i + i]), max(a[0*i :0 * i + i])
                    )
                )
            
        if all(ans == 
               sum(
                   [min(a[i2*i :i2 * i + i]), 
                   max(a[i2*i :i2 * i + i])]
                   ) for i2 in range(n) if i2 * i + i <= n):
        #만약 i 가 3이라면 a[0 : 3] a [3 : 6] a [6 : 9]
            print(1)
            quit()
            
print(0)