백준 32625 (C++) 분할

최초 업로드: 2025-10-04 07:19:31

최근 수정 시간: 2025-10-04 07:20:26

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 분할

[문제 링크](https://www.acmicpc.net/problem/32625)

## 문제 설명

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

## 입력

첫째 줄에 배열의 크기 $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의 약수를 √N 시간동안 찾고, 찾은 모든 약수를 길이로 두고 최솟값+최댓값이 같은지 판별하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int a[100'000];

int getMinMax(int l, int r) {
 int minVal=100'000, maxVal=0;
 for(int i=l;i<=r;i++) {
 minVal = min(minVal, a[i]);
 maxVal = max(maxVal, a[i]);
 }
 return minVal+maxVal;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<n;i++) cin >> a[i];

for(int sz=1;sz*sz<=n;sz++) {
 if(n%sz==0) {
 vector<int> v;
 for(int i=0;i<n;i+=sz) {
 v.push_back(getMinMax(i, i+sz-1));
 if(v.front()!=v.back()) break;
 }
 if(v.front()==v.back()) {
 cout << 1;
 return 0;
 }

if(sz!=1) {
 v = {};
 for(int i=0;i<n;i+=n/sz) {
 v.push_back(getMinMax(i, i+n/sz-1));
 if(v.front()!=v.back()) break;
 }
 if(v.front()==v.back()) {
 cout << 1;
 return 0;
 }
 }
 }
 }
 cout << 0;
}
```