https://www.acmicpc.net/problem/1377
정렬 문제처럼 보이지만 아이디어를 요구하는 애드혹 문제입니다.
이 문제는 버블 소트의 특징을 이해하고 있어야 풀 수 있습니다.
이해하고 있어도 문제를 해결하는데 필요한 아이디어를 얻기까지 꽤 오랜 시간이 걸렸습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
bool changed = false;
for (int i=1; i<=N+1; i++) {
changed = false;
for (int j=1; j<=N-i; j++) {
if (A[j] > A[j+1]) {
changed = true;
swap(A[j], A[j+1]);
}
}
if (changed == false) {
cout << i << '\n';
break;
}
}
|
cs |
우선 문제에 작성되어있는 코드로 i가 어떻게 출력되는지 찾아야 합니다.
우선 위 코드는 앞에 위치한 수가 자신보다 크다면 두 수의 위치를 변경하는 방식으로 구현된 정렬입니다.
이 로직에 의하면 범위 내 상대적으로 큰 수는 뒤쪽으로 이동하고, 상대적으로 작은 수는 앞쪽으로 이동하게 됩니다.
여기서 잡을 수 있는건 뒤쪽으로는 무한정 이동이 가능하지만 앞쪽으로는 한 칸만 이동이 가능하다는 것입니다.
즉 i가 한 번 돌아갈 때마다 상대적으로 작은 수는 앞쪽으로 한 칸 이동한다는 말이 되고, 앞쪽으로 가장 많이 움직인 횟수를 구하면 답을 얻을 수 있습니다.
여기까지 오셨다면 코드를 작성할 수 있습니다.
앞쪽으로 얼마나 이동했는지에 대해,
최초 위치한 인덱스를 저장할 필요가 있을 것이고,
정렬 후에 위치한 인덱스만 있다면 답을 구할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
#include <algorithm>
#define MAX 500001
using namespace std;
typedef pair<int, int> pii;
pii list[MAX];
int N;
void func() {
sort(list, list + N);
int ret = 0;
for (int i = 0; i < N; i++) {
ret = max(ret, list[i].second - i);
}
cout << ret + 1 << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i].first;
list[i].second = i;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |