[C++] 백준 1722번 순열의 순서
문제 링크
문제 요약
1부터 N까지의 수에 대해서 다음 두 가지 중 하나를 구한다.
1. 입력받은 수열이 몇 번째 순열인지
2. K번째 순열
접근 방법
std::next_permutation을 안다면 std::next_permutation을 K번 호출하는 풀이를 생각해 볼 수도 있습니다. 하지만 이 문제의 N은 최대 20이고 은 대략 정도이기 때문에 시간초과가 날 수밖에 없습니다.
따라서 몇번째 순열인지 직접 추적하되 중간 과정은 팩토리얼을 이용해서 넘기는 식으로 답을 구해야 합니다.
3 2 4 1
위의 수열이 몇 번째 순열인지 구하는 과정을 생각해보겠습니다.
List : [1, 2, 3, 4]
Now : [?, ?, ?, ?]
Target : [3, 2, 4, 1]
위에서부터 차례로
- 사용되지 않은 수의 리스트
- 현재 만들고 있는 순열의 상태
- 만들고자하는 순열입니다.
여기서 Now의 첫 자리에 들어와야하는 수는 Target에서 볼 수 있듯이 3입니다. 이 3이라는 수는 List의 세번째 원소입니다. 그렇기 때문에 적어도 현재 자리에 1 또는 2가 오는 순열들은 모두 건너뛸 수가 있습니다.
맨 앞 자리 숫자를 임의의 수로 고정시키면 남은 자리는 3개가 되고, 세 개의 수로 만들 수 있는 순열의 수는 이 됩니다. 따라서 현재 자리의 숫자가 3인 순열은 적어도 현재 자리가 1 또는 2인 순열의 수인 보다는 크다는 것을 알 수 있습니다. 이 를 결과에 더해줍니다.
List : [1, 2, 4]
Now : [3, ?, ?, ?]
Target : [3, 2, 4, 1]
Now의 맨 앞 자리를 3으로 갱신한 상태입니다. 따라서 List에서는 3이 제거되었습니다.
이번에 Now의 두번째 자리에 와야할 수는 2로, List의 두번째 원소입니다. List에서 2보다 작은 수인 1이 현재 자리에 오는 경우 만들 수 있는 순열의 수는 개 입니다.
List : [1, 4]
Now : [3, 2, ?, ?]
Target : [3, 2, 4, 1]
List : [1]
Now : [3, 2, 4, ?]
Target : [3, 2, 4, 1]
List : []
Now : [3, 2, 4, 1]
Target : [3, 2, 4, 1]
절차를 반복하면 결과적으로 Now와 Target이 같아지게 됩니다.
매 반복마다 (넣어야 하는 숫자의 리스트에서의 위치) * (남은 자리 수)!을 더해주면 몇번째 순열인지 구할 수 있습니다.
마찬가지로 이 절차를 응용하면 다른 질의 역시 해결할 수 있습니다.
코드
#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
long long factorial(int num)
{
long long ret = 1;
for (int i = 1; i <= num; i++)
ret *= (long long)i;
return ret;
}
int main(void)
{
FASTIO;
int n, q;
cin >> n >> q;
list<int> ls;
for (int i = 1; i <= n; i++)
ls.push_back(i);
if (q == 1)
{
long long k;
cin >> k;
vector<int> res;
for (int i = 1; i <= n; i++)
{
long long num = factorial(n - i);
for (list<int>::iterator it = ls.begin(); it != ls.end(); it++)
{
if (k - num <= 0)
{
res.push_back(*it);
ls.erase(it);
break;
}
k -= num;
}
}
VPRT(res, int);
}
else
{
vector<int> v(n + 1);
for (int i = 1; i <= n; i++)
cin >> v[i];
long long res = 0;
for (int i = 1; i <= n; i++)
{
long long num = factorial(n - i);
for (list<int>::iterator it = ls.begin(); it != ls.end(); it++)
{
if (*it == v[i])
{
ls.erase(it);
break;
}
res += num;
}
}
cout << res + 1;
}
return 0;
}
Author And Source
이 문제에 관하여([C++] 백준 1722번 순열의 순서), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beclever/C-백준-1722번-순열의-순서저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)