반응형
🔺 문제
🔺 코드
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
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M, K;
static int[][] D;
static int MAX = 1000000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken()); // "a" 개수
M = Integer.parseInt(st.nextToken()); // "z" 개수
K = Integer.parseInt(st.nextToken());
// DP 배열 채우기
D = new int[202][202];
for(int i = 0 ; i <= 200 ; i++) {
for(int j = 0 ; j <= i ; j++) {
if(j == 0 || j == i) {
D[i][j] = 1;
}
else {
D[i][j] = D[i - 1][j] + D[i - 1][j - 1];
if(D[i][j] > MAX) D[i][j] = MAX + 1;
}
}
}
// 불가능한 K인 경우 (= 사전에 수록된 문자열 개수 < K인 경우)
if(D[N + M][M] < K) {
System.out.println("-1");
}
else {
// 모든 문자를 사용할 때까지
while(!(N == 0 && M == 0)) {
int T = D[N - 1 + M][M]; // a를 선택하고 남은 문자로 만들 수 있는 모든 경우의 수
if(T >= K) { // a 선택하고 남은 문자로 만들 수 있는 모든 경우의 수가 K보다 크면
System.out.print("a"); // 현재 자리 문자를 a로 선택
N--;
}
else { // 모든 경우의 수가 K보다 작으면
System.out.print("z"); // 현재 자리 문자를 z로 선택
K -= T; // K를 계산된 모든 경우의 수를 뺀 값으로 저장
M--;
}
}
}
}
}
|
cs |
✅ 해결 아이디어
✔ 조합 & DP
💥 유의사항
• 두 문자로만 구성되어 있을 때, 이 문자들로 만들 수 있는 모든 경우의 수
= N + M 개에서 N/M개를 뽑는 경우의 수 (조합)
• 조합 점화식
D[ i ][ j ] = D[ i - 1 ][ j ] + D[ i - 1 ][ j - 1]
• 문자 선택 기준
(T : 현재 자릿수에서 a를 선택하고 남은 문자들로 만들 수 있는 모든 경우의 수)
⇨ T ≥ K : 현재 자리 문자를 a로 선택
⇨ T < K : 현재 자리 문자를 z로 선택 & K -= T로 업데이트
🔺 다른 풀이들
- 주석 설명 짱...
- 자세한 풀이 설명... 최고ㅠㅠ
💬 느낀 점
나에게는 너무 이해가 안 가는 조합....
사람이 이래서 수학을 잘하고 봐야하는 것 같다...고 느낌
으아악
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 7/3 |
(+ 7/4 2회독)
위 블로그 참고.........
복습을 50만번 해야할 거 같다...ㅋ
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
|
import java.util.*;
import java.io.*;
public class Main {
static double[][] dp = new double[101][101];
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken()); // a 개수
int M = Integer.parseInt(st.nextToken()); // z 개수
double K = Integer.parseInt(st.nextToken()); // K번쨰 문자열 구하기
if(check(N, M) < K) {
System.out.println(-1);
}
else {
getResult(N, M, K);
System.out.println(sb.toString());
}
}
// 개수 구하는 함수 (dp배열 채움)
private static double check(int a, int z) {
if(a == 0 || z == 0) return 1;
if(dp[a][z] != 0) return dp[a][z];
return dp[a][z] = Double.min(check(a-1, z) + check(a, z-1), 1000000001);
}
// 문자열 만드는 함수
private static void getResult(int a, int z, double k) {
if(a == 0) {
for(int i = 0 ; i < z ; i++) {
sb.append("z");
}
return;
}
if(z == 0) {
for(int i = 0 ; i < a ; i++) {
sb.append("a");
}
return;
}
double check = check(a-1, z);
if(k > check) {
sb.append("z");
getResult(a, z-1, k-check);
}
else {
sb.append("a");
getResult(a-1, z, k);
}
}
}
|
cs |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1463번: 1로 만들기 (0) | 2023.05.14 |
---|---|
[백준/JAVA] 1947번: 선물 전달 (0) | 2023.05.11 |
[백준/JAVA] 1722번: 순열의 순서 (0) | 2023.05.11 |
[백준/JAVA] 13251번: 조약돌 꺼내기 (0) | 2023.05.10 |
[백준/JAVA] 1010번: 다리 놓기 (0) | 2023.05.10 |