조합 예제 - 6
문제 분석
조합 문제와는 다르게 순열의 개념을 알아야 풀 수 있다.
순열은 순서가 다르면 다른 경우의 수로 인정한다. N자리로 만들 수 있는 순열의 경우의 수를 구해야 한다는 것이 문제의 핵심이다.
가장 먼저 각 자리에서 사용할 수 있는 경우의 수를 구한다.(예: N = 4)
1번째 자리 : 앞에서부터 채운다고 가정하면 제일 앞에서 사용할 수 있는 수는 4가지다.(1, 2, 3, 4)
2번째 자리 : 앞자리에서 사용한 수를 제외한 수를 사용할 수 있으므로 사용할 수 있는 수는 3가지
3번째 자리 : 앞자리에서 사용한 수 2개를 제외한 수를 사용할 수 있으므로 사용할 수 있는 수는 2가지
4번째 자리 : 앞자리에서 사용한 수 3개를 제외한 수를 사용할 수 있으므로 사용할 수 있는 수는 1가지
이렇게 각 자리에서 구한 경우의 수를 모두 곱하면 모든 경우의 수가 나온다.
4자리로 표현되는 모든 경우의 수는
4 * 3 * 2 * 1 = 4! = 24이다.이를 일반화하면 N자리로 만들 수 있는 순열의 모든 경우의 수는
N!이라는 것을 알 수 있다.
손으로 풀어보기
자릿수에 따른 순열의 경우의 수를 1부터 N자리까지 미리 계산한다.
소문제 1, K번째 순열 출력하기
K번째 순열 출력하기
주어진 값(K)과 현재 자리수(N) - 1에서 만들 수 있는 경우의 수를 비교한다.
a번에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다.(순열의 순서를 1씩 늘림)
K가 더 작아지면 순열에 값을 저장하고 K를
K = K - (경우의 수 * (cnt - 1))로 업데이트한다.순열이 완성될 때까지 a ~ c 과정을 반복하고 완료된 순열을 출력한다.
소문제 2, 입력된 순열의 순서 구하기
입력된 순열의 순서 구하기
현재 자릿수의 숫자를 확인하고 해당 숫자보다 앞 숫자 중 미사용 숫자를 카운트한다.
미사용 숫자 개수 * (현재 자리 - 1에서 만들 수 있는 순열의 개수)를 K에 더한다.모든 자릿수에 관해 과정 a ~ b를 반복하고 K 값을 출력한다.
슈도코드
factorial(자리별로 만들 수 있는 경우의 수 : 팩토리얼 형태)
permut(순열 리스트)
visit(숫자 사용 여부 리스트)
n(순열의 길이)
# factorial 초기화
for i 1 ~ n:
factorial[i] = factorial[i - 1] * i
data(문제 종류 및 순열 데이터 입력)
if data[0] == 1: # 순열 출력 문제
k(몇 번째 순열을 출력할지) # 길이가 n인 순열의 k번째 순서의 순열
for i n만큼:
cnt = 1 # 해당 자리에서 몇 번째 숫자를 사용해야 할지를 정하는 변수
for j n만큼:
이미 사용한 숫자는 pass
if 현재 순서 < 해당 자리 순열 수 * cnt:
현재 순서 = 현재 순서 - 해당 자리 순열 수 * (cnt - 1)
현재 자리(permut[i])에 j값 저장
숫자 j 사용 숫자 표시
반복문 종료
cnt 1 증가
permut 출력
else: # 순열의 순서를 출력하는 문제
k(순열의 순서 저장 변수)
for i n만큼:
cnt(0으로 초기화)
for j data[i]의 수만큼:
if 미사용 숫자:
cnt 1 증가 # 미사용 숫자 1 증가
k = k + cnt * 현재 자릿수에서 만들 수 있는 경우의 수
data[i]번째 숫자를 사용 숫자로 변경
k 출력코드 구현 - 파이썬
factorial = [0] * 21
permut = [0] * 21
visit = [False] * 21
n = int(input())
factorial[0] = 1
for i in range(1, n + 1):
factorial[i] = factorial[i - 1] * i
data = list(map(int, input().split()))
if data[0] == 1:
k = data[1]
for i in range(1, n + 1):
cnt = 1
for j in range(1, n + 1):
if not visit[j]: # N자리의 순열을 정할 때는 N-1번째 순열의 경우의 수를 이용한다.
# 주어진 k에 따라 각 자리에 들어갈 수 있는 수 찾기
if k <= cnt * factorial[n - i]: # 주어진 값(k)과 현재 자리 - 1에서 만들 수 있는 경우의 수 비교
k -= factorial[n - i] * (cnt - 1) # k가 더 작아지면 k를 k = k - 경우의 수 * (cnt - 1)로 업데이트한다.
permut[i] = j # k가 더 작아지면 순열에 값을 저장한다.
visit[j] = True
break
cnt += 1
for i in range(1, n + 1):
print(permut[i], end=' ')
else:
k = 1
for i in range(1, n + 1):
cnt = 0
for j in range(1, data[i]):
if not visit[j]: # 현재 자릿수의 숫자를 확인하고 해당 숫자보다 앞 숫자 중 미사용 숫자를 카운트
cnt += 1
k += cnt * factorial[n - i] # 미사용 숫자 * (현재 자리 - 1에서 만들 수 있는 순열의 개수) 를 k에 더한다.
visit[data[i]] = True
print(k)코드 구현 - 자바
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//각 자리마다 가능한 경우의 수
long[] factorial = new long[21]; //팩토리얼을 진행하면서 값이 커지므로 long 사용
boolean[] visit = new boolean[21];
int n = Integer.parseInt(br.readLine());
int[] result = new int[n];
factorial[0] = 1;
for (int i = 1; i < 21; i++) {
factorial[i] = factorial[i - 1] * i;
}
StringTokenizer st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
//k번째 수열 찾기
if (num == 1) {
// 최대 20!로 long으로 받아야 함
long k = Long.parseLong(st.nextToken());
//n자리 수 탐색
for (int i = 0; i < n; i++) {
for (int j = 1; j < n + 1; j++) {
if (visit[j]) { //이미 사용한 숫자는 continue
continue;
}
//각 자리의 경우의 수는 이전 자리의 경우의 수에 영향을 받음
if (factorial[n - i - 1] < k) { //이전 자리의 경우의 수와 k를 비교
/**
* k가 더 크다는 것은
* 현재 자리에 해당하는 숫자를 결정할 떄,
* 남은 경우의 수보다 큰 순서를 찾아야 한다는 것을 의미
* --------------------------------------------------
* k가 더 큰 경우 이전 자리의 경우의 수를 빼는 이유
* 대상 자리에 대한 경우의 수를 결정할 떄 이미 이전 자리에서 고려되었던 경우의 수를 제외하고
* 새로운 경우의 수를 고려해야하기 때문
*/
k -= factorial[n - i - 1];
} else {
/**
* k가 더 작다는 것은
* 현재 자리에 해당하는 숫자를 결정할 때,
* 이미 이전 자리에서 고려되었던 경우의 수를 포함하여 현재 자리에 올 수 있는 숫자의 범위 안에서 결정할 수 있다는 것을 의미
*/
result[i] = j;
visit[j] = true;
break;
}
}
}
for (int i = 0; i < n; i++) {
System.out.print(result[i] + " ");
}
//몇 번째 수열인지
} else {
long k = 1L; //순열의 순서
int[] arr = new int[n]; //순열을 구성하는 각 숫자
for (int i = 0; i < n ; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < arr[i]; j++) { //각 자리마다 해당 숫자가 순열에서 몇 번째로 작은 숫자인지를 계산
if (!visit[j]) {
k += factorial[n - i - 1];
}
}
visit[arr[i]] = true;
}
System.out.println(k);
}
}
}Last updated