문제
동혁이는 a가 N개, z가 M개로 이루어진 문자열을 사전 순으로 나열했다. 이 사전에서 K번째 문자열을 찾는 문제이다. 사전에 없는 경우(K가 전체 문자열 수를 초과하는 경우) -1을 출력한다.
입력
첫째 줄에 N, M, K가 주어진다 (1 ≤ N, M ≤ 100, 1 ≤ K ≤ 10^9).
출력
첫째 줄에 K번째 문자열을 출력한다. K가 사전의 크기보다 크면 -1을 출력한다.
예제
입력
2 2 2출력
aazz풀이
핵심 아이디어: a가 i개, z가 j개 남았을 때 만들 수 있는 문자열 수는 C(i+j, i)이다. 이를 이용해 현재 위치에서 a를 선택할 경우의 문자열 수와 K를 비교해 문자를 하나씩 결정한다.
dp[i][j]=a가 i개,z가 j개로 만들 수 있는 문자열 수 =C(i+j, i)로 정의한다.dp[i][j]가10^9를 초과하면10^9+1로 cap을 씌워 오버플로우를 방지한다.- 재귀적으로 문자 결정:
a를 선택했을 때 가능한 문자열 수:dp[a-1][z]K ≤ dp[a-1][z]이면a를 선택하고(a-1, z, K)로 진행K > dp[a-1][z]이면z를 선택하고(a, z-1, K - dp[a-1][z])로 진행
a또는z가 0이 되면 나머지 문자를 전부 채운다.- 최초 확인에서
dp[N][M] < K이면-1을 출력한다.
코드
import java.io.*;
import java.util.*;
public class Day370BOJ1256사전 {
static int N, M;
static double K;
static double[][] dp;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
dp = new double[N + 1][M + 1];
recur(N, M, K);
if (check(N, M) < K)
System.out.println(-1);
else
System.out.println(sb.toString());
br.close();
}
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 recur(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");
recur(a, z - 1, k - check);
} else {
sb.append("a");
recur(a - 1, z, k);
}
}
}복잡도
- 시간: O(N×M) — dp 테이블 채우기 및 재귀 호출 깊이 N+M
- 공간: O(N×M) — dp 테이블 저장