백준 BOJ 1377 - 버블 소트

추천받아서 풀어본 그리디 문제.

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

1377번: 버블 소트

처음에는 lis인가 생각했었는데 일단 이건 아니었다.

만약 swap 연산 후에 break 했다면 lis였을지도?

어떠한 숫자가 뒤로 가는 연산은 j 루프 한번으로 충분하기때문에

교환한 원소의 갯수를 기준으로 생각하면 정답에 도달하기가 힘들다.

 

어떠한 숫자 K에 대해서 swap을 진행한다고 할때,

지문에 나온 코드를 통해서 정렬하면

 

K는 j에 대한 루프가 도는동안

앞으로는 한칸 이동할 수 있고

뒤로는 무제한하게 이동할 수 있다.

 

따라서 뒤로 이동하는 부분을 무시하고,

정렬한 배열과 정렬전의 배열에서 인덱스를 비교해서,

앞으로 이동한 칸수의 최댓값을 찾으면,

그 칸만큼 "앞으로" 이동하기 위해서 해당 횟수만큼의 j 루프가 돈것이기 때문에

문제에서 원하는 정답을 얻어낼 수 있다.

 

정답은 앞으로 이동한 칸수의 최댓값 + 1 ( i는 1부터 시작하기에 )

 

#include <bits/stdc++.h>
using namespace std;

vector <pair<int,int>> A;

vector <int> lis;

int main(){
	int N,k;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> k;
		A.push_back({k,i});
	}
	
	int ans = -998244353;
	sort(A.begin(), A.end());
	for(int i=0; i<N; i++){
		ans = max(ans, A[i].second-i);
	}
	
	cout << ans+1;
	return 0;
}