문제 링크: https://www.acmicpc.net/problem/10973
10973번: 이전 순열
첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
주어진 순열의 이전 순열을 구하는 문제이다.
prev_permutation이라는 함수를 이용하였고, 그 이용방법은 next_permutation과 동일하다.
예를 들어, 1 2 4 3 네개의 숫자가 배열 혹은 벡터에 들어있다고 하자.
prev_permutation(a, a + n) 혹은 prev_permutation(v.begin(), v.end())를 실행하면 네개의 숫자가 1 2 3 4 이전 순열로 바뀌게 되고 함수는 true를 리턴한다. 만일 주어진 네개의 숫자가 1 2 3 4, 그러니까 가장 처음 순열이면 4 3 2 1로 바뀌게 되고 함수는 false를 리턴한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <bits/stdc++.h>
using namespace std;
int n, a[10001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
if(prev_permutation(a, a + n)) {
for(int i = 0; i < n; i++)
cout << a[i] << ' ';
cout << '\n';
}
else cout << -1 << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'재귀, 백트래킹 (Recursion, Backtracking)' 카테고리의 다른 글
백준 10819 차이를 최대로 (0) | 2020.05.04 |
---|---|
백준 10974 모든 순열 (0) | 2020.05.04 |
백준 10972 다음 순열 (0) | 2020.05.04 |
백준 15657 N과 M (8) (0) | 2020.05.04 |
백준 15656 N과 M (7) (0) | 2020.05.04 |