인접한 두 수를 분해하여 적절하게 바꿔서 정렬하는 방법

33708번: 인수분해 정렬

 

두 수 A[i]와 A[i+1]을 a*b = A[i]*A[i+1], a+b != A[i]+A[i+1]을 만족하는 a,b로 바꿀 때

 

원하는 만큼 이 연산을 시행해서 주어진 수열 A를 비내림차순으로 바꿀 수 있는가?

 

-------------------------------------------------------------------------------------------------------------------------------------------

 

a = 1, b = A[i]*A[i+1]이라고 하면, A[i],A[i+1]을 반드시 1,A[i]*A[i+1]

 

반대로 a = A[i]*A[i+1], b = 1이라고 하면 A[i],A[i+1]을 반드시 A[i]*A[i+1],1로 만들 수 있다

 

즉 A[1], A[2], A[3],...,A[n]이 주어지면 적절하게 두 수를 선택해서 한쪽으로 곱을 몰아줄 수 있다

 

즉, 1,1,1,1,...,A[1]*A[2]*A[3]*...A[n]으로 만들면 비내림차순으로 만들 수 있다

 

그런데, a+b != A[i] + A[i+1]이어야한다.

 

a*b = A[i]*A[i+1]이고 a+b = A[i] + A[i+1]이라면, b = A[i]+A[i+1] - a이므로

 

a(A[i]+A[i+1]) - a^2 = A[i]*A[i+1]

 

a^2 - a(A[i]+A[i+1]) +A[i]*A[i+1] = 0

 

(a - A[i])(a - A[i+1]) = 0이므로, a = A[i]이거나 a = A[i+1]이다.

 

마찬가지로 b = A[i]이거나 b = A[i+1]이다.

 

즉, a*b = A[i]*A[i+1]이고 a+b = A[i]+A[i+1]이라는 것은 (a = A[i],b = A[i+1]), (a = A[i+1],b = A[i])

 

이렇게 될려면 두 수의 곱이 A[i]*A[i+1] = k가 소수여서 1 * k, k * 1이어가지고 (1,k), (k,1)로만 분해되거나

 

두 수의 곱이 A[i]*A[i+1] = 1이여서 (1,1)로 분해되는 경우만 가능하다.

 

그런 경우라면, A[i]*A[i+1] = k이고 k가 소수라면, A[i] = 1, A[i+1] = k 혹은 A[i] = k, A[i+1] = 1이고

 

(a,b) = (1,k)만 가능하고, 그래서 a+b = 1+k = A[i] + A[i+1]로 조건을 만족하지 못한다.

 

두 수의 곱 A[i]*A[i+1] = 1인 경우도 마찬가지로 A[i] = 1, A[i+1] = 1, a = 1, b = 1만 가능하므로,

 

a + b = A[i] + A[i+1]이므로 조건을 만족하지 못한다

 

만약에 A[i]*A[i+1] = k가 합성수라면   a,b = 1,k로 하고 k는 A[i]*A[i+1]로 분해될 수 있으므로,

 

a+b = 1+k는 A[i]+A[i+1]과 다르다

 

따라서, 배열 A를 순회해서 인접한 두 수를 지정하고 두 수의 곱이 소수인지 아닌지 판단하면 된다.

 

만약 두 수의 곱이 합성수인 A[i],A[i+1]이 하나라도 존재하면 반드시 정렬이 가능하다.

 

그러면 (1,A[i]*A[i+1])으로 바꾸고, (A[i]*A[i+1], A[i+2])도 반드시 두 수의 곱이 합성수가 되어서 (1,A[i]*A[i+1]*A[i+2]),...

 

해서 한쪽으로 A[1],A[2],...A[i-1],1,1,1,...A[i]*A[i+1]*A[i+2]....A[n]으로 만들고...

 

다시 반대방향으로 A[1]*A[2]....A[n],1,1,1,1,...,1로 만든다음,

 

다시 반대방향으로 1,1,1,1,...,A[1]*A[2]*....A[n]으로 만들면 가능

 

두 수의 곱이 소수인지 합성수인지 판단하기 위해 10^6이내의 소수를 에라토스테네스의 체로 모두 구해놓으면

 

A[i],A[i+1]에 대하여

 

1) A[i]가 소수이거나 A[i+1] = 1

 

2) A[i]가 1이거나 A[i+1]이 소수

 

3) A[i]가 1이거나 A[i+1]이 1인 3가지는 O(1)에 판단할 수 있게 된다

 

물론 두 수의 곱이 모두 소수인 경우이지만 애초에 수열 A가 비내림차순이면 YES를 내야한다

 

def get_prime(n):
    
    result = [1]*(n+1)
    result[0] = 0
    result[1] = 0

    for i in range(2,int(n**(1/2))+1):
        
        if result[i] == 1:
            
            for j in range(i*i,n+1,i):
                
                result[j] = 0
    
    return result

def check(A):
    
    x = A[0]

    for i in range(1,n):
        
        if x > A[i]:
            
            return False
        
        x = A[i]
    
    return True

n = int(input())

A = list(map(int,input().split()))

prime = get_prime(10**6)

no = True

for i in range(n-1):
    
    x,y = A[i],A[i+1]

    if (x == 1 and prime[y] == 1) or (prime[x] == 1 and y == 1) or (x == 1 and y == 1):
        
        continue
    
    else:
        
        no = False
        break

if no:
    
    if check(A):
        
        print('YES')
    
    else:

        print('NO')

else:
    
    print('YES')