백준 1083 소트 (c++) : 피너클

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

1083번: 소트

그리드를 이용한 문제다.

예제 2를 예로 들어보면 아래 그래프 상태에서 s는 2인 상황에이다.

3

5

1

2

4

총 2번 움직일수 있는 상태에서 움직일수 있는 범위는 파란색 만큼이다.

3

5

1

2

4

3을 선택하면 0번 움직이는거고 5를 선택하면 1번 움직이는거, 1을 선택하면 2번 움직이는 것이다.

가장 최선의 움직이는 방법은 5를 선택해 1번 움직이는 것이다.

5

3

1

2

4

이제 s는 1인 상황이다. 배열의 첫번째는 최선의 상태니 두번째에서 시작한다.

5

3

1

2

4

두번째에서 가장 최선의 움직이는 방법은 3을 선택해 0번 움직이는 것이다.

이제 s는 1인 상황이다. 배열의 두번째는 최선의 상태니 세번째에서 시작한다.

5

3

1

2

4

세번째에서 가장 최선의 움직이는 방법은 2를 선택해 1번 움직이는 것이다.

5

3

2

1

4

이제 s가 0이니 배열을 출력하면 된다.

최대로 움직일수 있는 횟수가 s이니 무조건 s를 채워야 하는것이 아니다. s보다 많이만 움직이지 않으면 된다.

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

입력은 이렇게 받는다.

for (int i = 0; i < n && s > 0; i++) {

int i는 바꿀 배열의 위치를 나타낸다. 만약 i가 n과 같거나 커지면, 즉 배열을 넘어가게 되면 반복문을 종료하고

그와함께 만약 s가 0과 같거나 작아지면, 즉 더이상 움직일수 없는 상태가 되면 반복문을 종료한다.

	int idx = i, m = arr[i];
	for (int j = i + 1; j < n && j - i <= s; j++) {
		if (arr[j] > m) {
			m = arr[j];
			idx = j;
		}
	}

int idx는 바꿀 배열의 위치, m은 바꿀 배열의 크기를 뜻한다.

int j는 i + 1부터 n까지, 혹은 j - i <= s, 즉 최대로 움직일수 있는 만큼 늘어난다.

만약 arr[j]가 m보다 크다면 움직일수 있는 범위안의 가장 큰 숫자라는 뜻이니

m을 arr[j]로 바꾸고 idx를 j로 바꾼다.

	if (idx != i) {
		s -= (idx - i);
		for (int j = idx; j > i; j--) {
			arr[j] = arr[j - 1];
		}
		arr[i] = m;
	}		
}

만약 idx가 i가 아니라면, 즉 현재 배열보다 더 큰 배열이 뒤에 있다면

s에서 idx - i만큼 (움직이는 횟수) 빼준다.

그후 배열을 하나씩 뒤로 미룬다.

1

2

3

4

5

5를 가장 앞으로 옮긴다고 생각하면 현재 m에 5가 저장되어있는 상태다.

1

2

3

4

4

arr[4]에 arr[3]을 집어넣고

1

2

3

3

4

arr[3]에 arr[2]를 집어넣는다. 이 순서대로 반복하면

1

1

2

3

4

위와 같은 배열이 만들어지니 마지막에 m에 저장되어있는 5를 arr[0]에 넣어준다. 그러면

5

4

3

2

1

위와 같이 만들어진다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

int n, s;
int arr[51];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

	for (int i = 0; i < n && s > 0; i++) {
		int idx = i, m = arr[i];
		for (int j = i + 1; j < n && j - i <= s; j++) {
			if (arr[j] > m) {
				m = arr[j];
				idx = j;
			}
		}

		if (idx != i) {
			s -= (idx - i);
			for (int j = idx; j > i; j--) {
				arr[j] = arr[j - 1];
			}
			arr[i] = m;
		}		
	}
	for (int i = 0; i < n; i++) cout << arr[i] << ' ';
}

전체코드다.