[프로그래머스] 줄 서는 방법

링크

https://programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

풀이

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 구하는 문제이다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 22
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

ll dp[SIZE];
vector<int> num;
vector<int> solution(int n, long long k) {
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1] * i;
		num.push_back(i);
	}

	vector<int> answer;
	
	k--;
	while (!num.empty()) {
		if (k == 0) {
			answer.push_back(num[k]);
			num.erase(num.begin());
			continue;
		}
		ll mok = k / dp[n-1];
		ll na = k % dp[n-1];

		answer.push_back(num[mok]);
		num.erase(num.begin() + mok);
		k = na; n--;

	}
	return answer;

}