BOJ 1377 - 버블소트

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

똑같은문제:https://www.acmicpc.net/problem/15760

<문제설명>

무작위 배열이 주어진다. 몇번째 라운드에 버블소트가 종료되는지 구하라

 

<풀이>

원소가 스왑되어 움직이는 그림을 생각해 보자. 한 라운드에 원소는 우측으로는 제한없이 이동가능하지만, 왼쪽으로는 한 라운드에 최대 한 칸만 움직일 수 있다.

 

정렬 전 상태->정렬 후 상태를 비교했을 때 왼쪽으로 최대 이동한 원소의 이동횟수+1이 정답

 

<코드>

int main() {
	int n,ans=0;
	scanf("%d", &n);
	vector<P> a(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i].first);
		a[i].second = i; // original
	}
	sort(a.begin(), a.end());
    
	for (int i = 0; i < n; i++) 
    	ans=max(ans,a[i].second-i);
	
	printf("%d\n", ans + 1);
	return 0;
}