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<intint> 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

'algorithm > ad-hoc' 카테고리의 다른 글

boj 5527 전구 장식  (0) 2024.07.30
boj 14864 줄서기  (0) 2024.07.26
boj 2381 최대 거리  (0) 2024.07.25
boj 14675 단절점과 단절선  (0) 2024.07.23
boj 27468 2배 또는 0.5배  (0) 2024.07.22

+ Recent posts