3231 카드놀이

이 문제는 규칙성을 생각해보면 풀 수 있는 문제로,

여러개의 (N개의) 카드를 탐색해가며 가장 오른쪽 끝에서 왼쪽으로, 즉 한쪽 끝까지 탐색을 완료했을 때를 count 해주는 문제이다.

처음에 N개의 카드에 각각의 위치를 저장하고, 현재 count 해야하는 카드가 다음 count해야 하는 카드의 위치보다 오른쪽에 있다면

한쪽 끝까지 탐색 후 다시 가장 왼쪽으로 돌아가 탐색을 시작해야 하기 때문에 

이 경우에 cnt(박수 횟수) 를 증가시키면 된다.

예시로 3 2 5 4 1의 경우를 들어보자면, 우선 1과 2를 탐색하는 것만 간단한 그림으로 나타내 보았다.

1을 탐색 후 왼쪽 끝으로 돌아와 다시 2를 탐색해야 하기 때문에 박수를 한 번 친 후에 왼쪽 끝으로 이동해야하므로

이 과정에서 cnt가 1증가하게 된다.

 같은 방식으로 3, 4, 5를 탐색하면 된다.

간단한 문제이므로 추가적인 설명은 하지 않도록 하겠다.

<소스코드>

#include <cstdio>

int N, a,num[100001],cnt;

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &a);
		num[a] = i;
	}
	for (int i = 1; i < N; i++) {
		if (num[i] > num[i + 1]) cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}