백준 18900 (Printer's Head)

https://www.acmicpc.net/problem/18900

18900번: Printer's Head

 

임의의 배열이 주어진다. 숫자 배열에서 가장 큰 수 부터 지울 수 있는데, 여기서 지우는 조건은 1차이나는 숫자를 한 방향으로 지우는 것이다. 

 

만약 5 4 3 2 1

이 있다고 하면 5에서 printer을 켜서 한 번에 지울 수 있게 된다. 

 

이때 가장 최소의 printer 작동 횟수를 구하는 문제이다. 

 

가장 큰 것부터 차례대로 작동시키는 것이므로 배열에 해당 index를 저장시켜서 비교를 수월하게 하였다. 

 

그리고 방향을 정해줘야 하는데 오른쪽으로 갈지 왼쪽으로 갈지를 그 다음 숫자의 위치와 지금의 위치를 비교해서 정해주었다.

 

마지막으로 언제까지 printer가 작동되는지 변수의 크기에 유의해서 풀면된다. 

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

int n, cnt;
int arr[MAX];
bool goleft;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		arr[a] = i;
	}
	if (n == 1) {
		cout << 1 << "\n";
		return 0;
	}
	while (n >= 2) {
		if (arr[n - 1] < arr[n]) goleft = true;
		else goleft = false;
		if (goleft) {
			while (arr[n - 1] < arr[n]) {
				n--;
				if (n == 1)break;
			}
			n--;
			cnt++;
		}
		else {
			while (arr[n - 1] > arr[n]) {
				n--;
				if (n == 1)break;
			}
			n--;
			cnt++;
		}
	}
	if (n == 1) {
		cnt++;
	}
	cout << cnt << "\n";
}