# [Gold III] So☆Lucky [문제 링크](https://www.acmicpc.net/problem/34030) ## 문제 설명 <p>유이는 길이 $N$의 수열 $A$를 오름차순 정렬하려 한다. 그러나 평범한 정렬 알고리즘은 너무 뻔하다고 생각한 유이는 다음 두 가지 연산 중 하나만을 사용하여 수열을 정렬하려 한다.</p> <ul> <li>연산 $1$: $A_i, A_{i+1}$의 합이 홀수인 $i$를 골라 이 두 원소를 교환한다. $(1\leq i< N)$</li> <li>연산 $2$: $A_i, A_{i+1}$의 합이 짝수인 $i$를 골라 이 두 원소를 교환한다. $(1\leq i< N)$</li> </ul> <p>주어진 수열 $A$에 대해, 두 가지 연산 중 한 가지 연산만을 $0$번 이상 사용해서 오름차순 정렬이 가능하다면 유이는 자신이 운이 좋다고 생각하고, 불가능하다면 운이 나쁘다고 생각한다.</p> <p>유이는 지금 자신이 얼마나 운이 좋은지 알고 싶다. 당신이 대신 확인해주자.</p> ## 입력 <p>첫째 줄에 $N$이 주어진다.</p> <p>둘째 줄에 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다.</p> ## 출력 <p>첫째 줄에 연산 $1$만을 사용했을 때 유이의 운이 좋다면 <code>So Lucky</code>를, 운이 나쁘다면 <code>Unlucky</code>를 출력한다.</p> <p>둘째 줄에 연산 $2$만을 사용했을 때 유이의 운이 좋다면 <code>So Lucky</code>를, 운이 나쁘다면 <code>Unlucky</code>를 출력한다.</p> ## 풀이 - 홀짝, 짝홀 이 올 때 앞의 값이 항상 작아서 swap해야 하는 경우가 없는 경우 2번 연산만 사용하는 것이 가능하다. - 홀수는 홀수끼리, 짝수는 짝수끼리 오름차순으로 정렬되어 있으면 1번 연산만 사용하는 것이 가능하다. ``` c++ #include<bits/stdc++.h> using namespace std; int n, a[200'000]; bool isOdd() { int lastOdd=0, lastEven=0; for(int i=0;i<n;i++) { if(a[i]%2) { if(lastOdd>a[i]) return false; lastOdd=a[i]; } else { if(lastEven>a[i]) return false; lastEven=a[i]; } } return true; } bool isEven() { for(int i=0;i<n-1;i++) { if(a[i]%2!=a[i+1]%2 && a[i]>a[i+1]) return false; } return true; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0;i<n;i++) cin >> a[i]; cout << (isOdd() ? "So Lucky\n" : "Unlucky\n"); cout << (isEven() ? "So Lucky" : "Unlucky"); } ```