백준 20309번, 트리플 소트 풀이

문제

백준 20309번

풀이

길이가 3이 되도록 연속된 구간을 잡아서 reverse해서 배열을 오름차순으로 만들어야 합니다.

[a, b, c]라면 [c, b, a]가 됩니다.

 

조금 관찰하면, 중간의 수는 고정되있고 양끝의 수만 바뀌는 것을 볼 수 있습니다.

 

이를 이용하면, 홀수 자리에는 홀수만, 짝수 자리에 짝수만 오면 몇번이던 실행하여 정렬할 수 있습니다.

하지만 짝수 자리에 홀수(또는 홀수 자리에 짝수)가 오게 된다면 몇번 실행하던 홀수 자리에 있던 짝수가 짝수 자리로 갈 수 없습니다.

 

예를 들면, [2, 1, 3]과 같은 배열이 있는데 이 배열은 몇번이고 트리플 소트를 실행하더라도 1이 첫번째 자리로 갈 수 없습니다.

 

따라서, 짝수 자리에는 짝수만, 홀수 자리에 홀수만 오는지 확인해주면 됩니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	int f = 0;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		if (a % 2 != i % 2) {
			f = 1;
			break;
		}
	}
	cout << (f ? "NO" : "YES") << "\n";
}