[CodeForces] 1145A - Thanos Sort

문제 :  https://codeforces.com/contest/1145/problem/

---

[알고리즘풀이]

주어진 배열이 오름차순이 아니라면 배열을 반으로 자르는 과정을 반복해서

오름차순인 배열이 나오는 경우를 찾아야한다.

Input이 2의 n승으로 들어오고 값이 최대 16으로 굉장히 작으므로,

배열의 개수가 1, 배열의 크기가 N일 때부터 오름차순인지 아닌지 Check하며

배열의 개수를 2배씩 늘리고, 배열의 크기를 반으로 나누며 모든 경우를 Check한다.

#include<iostream>

using namespace std;

int A[50];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> A[i];

	int size = n, g = 1;
	while (1) {
		for(int i = 0; i < g; i++){
			bool check = false;
			for (int j = 1; j <= size - 1; j++) {
				if (A[size * i+ j] > A[size * i + j + 1]) {
					check = true;
					break;
				}
			}
			if (check == false) {
				cout << size;
				return 0;
			}
		}
		g *= 2;
		size /= 2;
	}
}

---