[Platinum V] 수 정렬하기, 근데 이제 제곱수를 곁들인 - 25323

문제 링크

성능 요약

메모리: 208424 KB, 시간: 1132 ms

분류

수학, 정렬, 애드 혹, 정수론

제출 일자

2025년 9월 15일 22:17:22

문제 설명

양의 정수로 이루어진 길이가 $N$ 인 수열 $A_1,A_2,\cdots ,A_N$이 존재할 때, 다음 행동을 원하는 만큼 반복할 수 있다.

$1\leq i,j\leq N;i\neq j$이면서 $A_i\times A_j$가 제곱수인 $i$, $j$를 선택해, $A_i$와 $A_j$의 값을 바꾼다.

위 행동을 원하는 만큼 반복하여 수열 $A_1,A_2,\cdots ,A_N$을 비내림차순, 즉 $A_1\le A_2\le\cdots\le A_N$가 되도록 정렬할 수 있는지 판단하시오.

입력

첫 번째 줄에 $N$이 주어진다. $(1\leq N\leq 500\, 000)$

두 번째 줄에 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. $(1\leq A_i\leq 10^{18})$

출력

위 행동을 원하는 만큼 반복하여 수열을 비내림차순으로 정렬할 수 있으면 YES, 아니면 NO를 출력하시오.

---

💡 해결 방법

💻 코드

import math
import sys
input = sys.stdin.readline
 
        
        
 
 
n = int(input())
list1 = list(map(int, input().split()))  
list_ans = sorted(list1[:])  
 
if list1 == list_ans:
    print("YES")
else:
    for i in range(len(list1)):
        if list1[i] != list_ans[i]:
            if not math.isqrt(list1[i] * list_ans[i]) ** 2 == list1[i] * list_ans[i]:
                print("NO")
                exit()
    
    print("YES")