https://www.acmicpc.net/problem/7982
순열 그래프는 N개의 정점이 1 ~ N의 번호가 하나씩 구성되어 있습니다.
그리고 두 정점 쌍 i, j (1 ≤ i < j ≤ n) 는 ai > aj 일때 간선으로 연결되어 있습니다.
4
2 3 1 4순열이 이렇게 주어졌을 때 2, 3 > 1이므로 (1, 2), (1, 3)이 각각 연결되어 있고
(1, 2, 3) (4) 로 집합을 나눌 수 있습니다.
여기서 알 수 있는건 i번째 까지 순회했을때 max가 i이면 해당 위치까지 하나의 집합으로 묶을 수 있습니다.
위의 예시로 보면
3번 인덱스까지의 max가 3이므로 1, 2, 3을 집합으로 묶을 수 있고, 4번 인덱스까지의 max가 4이므로 4를 집합으로 묶을 수 있습니다.
이전 집합의 max값을 유지해주면서 배열을 순회하면 정답을 구할 수 있습니다.
|
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
38
39
40
41
42
43
|
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;
vector<int> v;
int list[MAX];
int N;
void func() {
int maxValue = 0;
for (int i = 1; i <= N; i++) {
maxValue = max(maxValue, list[i]);
if (i == maxValue) v.push_back(i);
}
int pre = 0;
cout << v.size() << '\n';
for (auto x : v) {
cout << x - pre << ' ';
for (int i = pre + 1; i <= x; i++) cout << i << ' ';
cout << '\n';
pre = x;
}
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > ad-hoc' 카테고리의 다른 글
| boj 27966 △ (0) | 2024.08.22 |
|---|---|
| boj 16161 가장 긴 증가하는 팰린드롬 부분수열 (0) | 2024.08.15 |
| boj 24553 팰린드롬 게임 (0) | 2024.08.07 |
| boj 14370 전화번호 수수께끼 (Large) (0) | 2024.08.06 |
| boj 21316 스피카 (0) | 2024.08.05 |