본문 바로가기

재귀, 백트래킹 (Recursion, Backtracking)

백준 10973 이전 순열

문제 링크: 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