백준 33708 (C++) 인수분해 정렬

최초 업로드: 2025-04-14 12:25:33

최근 수정 시간: 2025-07-25 09:55:19

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 인수분해 정렬

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

## 문제 설명

쿠는 길이가 $N$인 수열 $A$를 가지고 있다. 쿠는 다음과 같은 연산을 통해 수열을 정렬하려고 한다.

<ul>
	<li>$1 \le i \lt N$인 $i$를 선택하여, $A_i$와 $A_{i+1}$을 각각 $a\times b= A_i \times A_{i+1}$과 $a+b \neq A_i+A_{i+1}$을 만족하는 두 양의 정수 $a$, $b$로 바꾼다.</li>
</ul>

연산을 원하는 만큼 시행하여, 수열을 비내림차순으로 만들 수 있는지 판별해 보자.

## 입력

첫째 줄에 수열의 길이를 나타내는 정수 $N$이 주어진다. $\left(2 \le N \le 200\, 000\right)$

둘째 줄에 $N$개의 정수 $A_1,\, A_2,\, \cdots,\, A_N$이 공백으로 구분되어 주어진다. $\left(1 \le A_i \le 10^6 \right)$

## 출력

수열 $A$를 비내림차순으로 만들 수 있다면 <code>YES</code>를, 그렇지 않다면 <code>NO</code>를 출력한다.

## 풀이
#### 소수 두 개가 붙어있거나, 합성수가 존재하면 비내림차순으로 정렬할 수 있다. 만들 수 있는 가장 쉬운 형태는 맨 마지막 수 빼고 전부 1로 만들면 된다.
#### ex) 10 1 1 -> 2 5 1 -> 1 10 1 -> 1 2 5 -> 1 1 10

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

const int MAX = 1000000;
int notPrime[MAX+1] = {true, false, false, }; // 1은 소수가 아니지만 예외로 false처리리
int a[MAX];

string chk(int n) {
 for(int i=0;i<n;i++) {
 if(notPrime[a[i]] || i>0 && a[i-1]!=1 && a[i]!=1) {
 return "YES";
 }
 }

for(int i=1;i<n;i++) {
 if(a[i-1]>a[i]) {
 return "NO";
 }
 }
 return "YES";
}

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 i=2;i*i<=MAX;i++) {
 if(!notPrime[i]) {
 for(int j=i*i;j<=MAX;j+=i) {
 notPrime[j]=true;
 }
 }
 }
 cout << chk(n);
}
```