백준 20127(Y-수열)

www.acmicpc.net/problem/20127

20127번: Y-수열

음 그냥 봤을때 그리디로 O(N)의 풀이가 생각난다. 일단 말로 표현을 해보자

 

처음부터 k개의 증가하는 부분수열을 맨뒤에 붙였을때 전체 수열이 증가하는 수열이 되도록 만드는 것이다. 

 

만약에 증가에 대해서 불가능 하려면 증가 감소 증가 감소 이런식으로 증가에서 감소가 되는 지점이 2개 이상이면 불가능 하다. 

따라서 우리는 수열이 증가하는지 감소하는지 판단해서 짜면 될것같다. 

그렇게 구현을 해보려고 했지만 상당히 난해한 구현때문에 뽸일 

 

잘 생각해보니 그냥 두가지 케이스를 가정하고 두가지 경우에 대해 모두 체크하면서 진행하면 된다.

 

처음이 증가하는 수열, 감소하는 수열 

 

나머지는 boolean자료형을 잘 사용해서 짜면 된다. 

 

문제가 상당히 괜찮은것같다. 

 

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 1000005

int N, bef, cnt1, cnt2;
int num[MAX];
bool check1, check2, cant1, cant2;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	bef = num[0];
	for (int i = 0; i < N; i++) {
		if (bef > num[i]) {
			if (!check1) {
				check1 = true;
			}
			else cant1 = true;
		}
		else if (bef < num[i]) {
			if (!check2) {
				check2 = true;
			}
			else cant2 = true;
		}
		if (bef <= num[i] && !check1) {
			cnt1++;
		}
		if (bef >= num[i] && !check2) {
			cnt2++;
		}
		bef = num[i];
	}
	if (num[0] > num[N - 1])cant2 = true;
	if (num[0] < num[N - 1])cant1 = true;

	if (cnt1 == N || cnt2 == N) {
		cout << 0;
	}
	else {
		if (cant1 && cant2) {
			cout << -1;
		}
		else if (!cant1 && !cant2) {
			cout << min(cnt1, cnt2);
		}
		else if (cant1) {
			cout << cnt2;
		}
		else if (cant2) {
			cout << cnt1;
		}
	}

}