반응형
🔺 문제
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
int N, Q;
long F[] = new long[21]; // 각 자리별로 만들 수 있는 경우의 수 저장 (팩토리얼 형태)
int S[] = new int[21]; // 순열 담는 배열
boolean visited[] = new boolean[21]; // 숫자 사용 유무 저장 배열
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine()," ");
Q = Integer.parseInt(st.nextToken());
// 팩토리얼 초기화 → 각 자리수에서 만들 수 있는 경우의 수
F[0] = 1;
for(int i = 1 ; i <= N ; i++) {
F[i] = F[i - 1] * i;
}
// 1) 순열 출력 문제
if(Q == 1) {
long K = Long.parseLong(st.nextToken()); // 현재 순서
// 팩토리얼 가짓수 치기
for(int i = 0 ; i < N ; i++) {
for(int j = 1 ; j <= N ; j++) {
if(visited[j]) continue;
// 주어진 K에 따라 각 자리에 들어갈 수 있는 수 찾기
if(F[N - i - 1] < K) { // N : 현재 자리
K -= F[N - i - 1];
}
else { // 해당하는 원소를 찾은 것
S[i] = j; // 현재 자리에 j값 저장
visited[j] = true;
break;
}
}
}
for(int i = 0 ; i < N ; i++) {
System.out.print(S[i] + " ");
}
}
// 2) 순서 출력 문제
else {
for(int i = 0 ; i < N ; i++) {
S[i] = Integer.parseInt(st.nextToken()); // 순열 배열 저장
}
long ans = 1;
for(int i = 0 ; i < N ; i++) {
for(int j = 1 ; j < S[i] ; j++) {
// 1부터 해당하는 원소까지 팩토리얼 값 늘려가며 더하기
if(visited[j]) continue;
ans += F[N - i - 1];
}
visited[S[i]] = true;
}
System.out.println(ans);
}
}
}
|
cs |
✅ 해결 아이디어
✔ 조합 & DP
- K번째 순열 출력하기
1) 주어진 값(K)과 현재 자리(N) - 1에서 만들 수 있는 경우의 수 비교
2) 1에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킴 (순열 순서를 1씩 증가)
3) K가 더 작아지면, 순열에 값을 저장하고, K를 K - (경우의 수 * (cnt - 1))
로 업데이트
4) 순열이 완성될 때까지 1~3을 반복하고 완료된 순열 출력
- 입력된 순열의 순서 구하기
1) N자리 순열의 숫자를 받아 몇 번째 순서의 숫자인지 확인 (현재 숫자 - 자기보다 앞 숫자 중 이미 사용한 숫자)
2) 해당 순서 * (현재 자리 - 1에석 만들 수 있는 순열의 개수)
를 K에 더함
3) 모든 자릿수에 관해 1~3을 반복한 후 K값 출력
🔺 다른 풀이들
- 복습용
- 약간 코드가 다름
💬 느낀 점
아앗... 머리가 안 돌아가.....
복습을 10번은 해봐야 할 것 같다....
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 7/3 |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1947번: 선물 전달 (0) | 2023.05.11 |
---|---|
[백준/JAVA] 1256번: 사전 (0) | 2023.05.11 |
[백준/JAVA] 13251번: 조약돌 꺼내기 (0) | 2023.05.10 |
[백준/JAVA] 1010번: 다리 놓기 (0) | 2023.05.10 |
[백준/JAVA] 11051번: 이항 계수 2 (0) | 2023.05.10 |