[ boj : 1083 ] 소트

www.acmicpc.net/problem/1083

1083번: 소트

문제 : 최대 s번을 움직일 수 있고 이때 사전순으로 가장 뒤에 나오는 수열을 구하여라, 이때 사전순은 그냥 가장 큰 수가 앞으로 오게끔 하면 됩니다.

 

해설 : 음....저에겐 구현을 어떻게 해야될지 해맸습니다.

일단 사실 접근은 그렇게 어렵지는 않아 보입니다. 현재 움직일 수 있는 범위 내에서 가장 큰 수를 선택한 후 맨 앞으로 옮기면 됩니다.

구현은...소스를 참고하시길!!!

 

#include<bits/stdc++.h>

using namespace std;

int arr[50];
bool check(int n);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n,m;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> arr[i];
	cin >> m;

	for (int i = 0; i < n && 0 < m; i++) {
		int Max = -1, index = -1;
		for (int j = i; j<n && j <= i + m; j++) {
			if (Max < arr[j]) {
				Max = arr[j];
				index = j;
			}
		}
		for (int j = index; j > i; j--) {
			swap(arr[j - 1], arr[j]);
			m--;
		}
	}
	for (int i = 0; i < n; i++)cout << arr[i] << " ";
	return 0;
}