728x90
82번 사전
내가 떠올린 풀이 해설
a와 z의 개수가 각각 N, M개일 때 이 문자들로 만들 수 있는 모든 경우의 수는 N + M 개에서 N개를 뽑는 경우의 수 또는 N + M개에서 M개를 뽑는 경우의 수와 동일하다. arr배열을 초기화하고, 점화식으로 값을 계산해 저장한다. 몇 번째 문자열을 표현해야 하는지를 나타내는 변수를 K라고 하자 현재 자릿수에서 a를 선택했을 때 남아 있는 문자들로 만들 수 있는 모든 경우의 수는 T이다. T와 K를 비교해 문자를 선택한다. 문자 선택 기준은 T >= K : 현재 자리 문자를 a로 선택 T < K : 현재 자리 문자를 Z로 선택하고, K = K - T로 업데이트
ex) a = 2, z = 2이고 a를 선택했을 때 나머지 문자열로 만들 수 있는 경우의 수는 arr[남은문자 총 개수 : 3][남은 z개수 : 2]
arr [3][2] = 3 >= k(2)이므로 a 확정 -> z는 2개 남음
arr [3][2] = 3 < k(2)이므로 z 확정 -> z는 1개 남음 -> K = K - T = 1로 업데이트
arr [1][1] = 1 >= k(1)이므로 a 확정 -> z는 1개 남음
arr [0][1] = 1 < k(2)이므로 z 확정
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1256 {
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());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int [][] arr = new int[202][202];
for(int i = 0; i <= 200; i++) { // 조합 테이블 초기화
for(int j = 0; j <= i; j++) {
if(j == 0 || j == i) {
arr[i][j] = 1;
}
else {
arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
if(arr[i][j] > 1000000000) { //k 범위가 넘어가면 범위의 최댓값
arr[i][j] = 1000000001;
}
}
}
}
if(arr[n + m][m] < k) { // 주어진 자릿수로 만들 수 없는 K번째 수이면
System.out.println(-1);
}
else {
// a를 선택했을 때 남은 문자로 만들 수 있는 모든 경우의 수가 K 보다 크면
while(!(n == 0 && m == 0)) {
if(arr[n - 1 + m][m] >= k) {
System.out.print("a");
n--;
}
else { // 모든 경우의 수가 k보다 작으면
System.out.print("z");
k = k - arr[n - 1 + m][m]; // k값 업데이트
m--;
}
}
}
}
}
오늘의 회고
오늘은 캐치 콘에서 하는 세미나 참가로 조합 문제 1문제를 풀었습니다. 이제 조합 문제 1문제가 남았고 이제 DP를 들어갈 차례입니다. DP까지 풀면 중요한 알고리즘은 다 풀었습니다. 개념 복습을 하면서 다시 문제 풀고 문제 복습을 하는 순서로 공부를 해야겠습니다.
728x90
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| Do it! 알고리즘 코딩 테스트(85번 ~ 86번) (0) | 2022.07.05 |
|---|---|
| Do it! 알고리즘 코딩 테스트(83번 ~ 84번) (0) | 2022.07.01 |
| Do it! 알고리즘 코딩 테스트 (80번 ~ 81번) (0) | 2022.06.29 |
| Do it! 알고리즘 코딩 테스트 (78번 ~ 79번) (0) | 2022.06.28 |
| Do it! 알고리즘 코딩 테스트 (76번 ~ 77번) (0) | 2022.06.27 |
