🎯 문제
🎯 입력 및 출력
🚀 풀이 방법
dp 문제를 풀이하는 방식으로 접근을 하여야 하지만, 좀 더 알아야 할 것이 있었습니다!
n개의 문자와 m개의 문자를 조합하여 만들 수 있는 문자열의 개수를 구할 수 있는 것이 시급하였습니다.
문자열의 개수를 구해야 하는 이유는 다양한데요!
(먼저 점화식은
dp[n][m] = dp[n-1][m]+dp[n][m-1] 로 도출 해 내었습니다.(n은 문자 'a'의 개수, m은 문자 'z'의 개수) )
가장 첫 번째 이유는 출력의 조건을 맞추기 위해서 입니다.
출력의 조건으로는 "첫째 줄에 규완이의 사전에서 k번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 k 보다 작으면 -1을 출력한다." 의 조건으로 인해 문자열의 개수를 구해야합니다.
두번 째 이유로는 (문제 풀이의 핵심!!)
자릿 수가 a가 올 것인지 z가 올 것인지 판단하기 위해 서입니다.
('a'문자가 삽입될 때 가능한 문자열의 개수를 판단하여 지금 자릿 수에 'a'가 올 것인지 'z'가 올 것인지를 결정!)
제가 봐도 이해가 안가니
예를 한번 들어 보죠
a문자 3개와 z문자 2개가 이루어져 있을 때 k가 4인 경우
만들 수 있는 경우의 수를 나열해 보면
1. aaazz
2. aazaz
3. aazza
4. azaaz
5. azaza
6. azzaa
7. zaaaz
...
이런 식으로 나올 것입니다.
그렇다면 일단, k가 4인 경우이니 일단은 'a'로 시작하는 문자열이 와야합니다. 'a'로 시작하는 문자열의 개수는 6입니다. 이제부터는 1번에서 6번까지 에서만 판단하면 됩니다.
그 다음을 보죠.. 여기서 "aa"로 시작하는 문자열의 개수를 봅시다! 1번에서 3번 까지 입니다. 음.. k는 4였죠!! 4번째 문자열이 와야하는데 이 조건에 타당하지 않은 것입니다.
그러니 'z'가와 야하는 것입니다!
이제 "az"로 시작하는 문자열은 4~6번 까지로 확인 되었습니다. 이제 k는 4~6번 째 중 첫번 째를 고르면 되죠??
k는 4였으니 "aa"로 시작하는 문자열의 개수 3을 딱!! 빼주면 됩니다..
죄송해요.. 제가 말 주변이 없어서 설명드릴 수 있는 부분은 여기 까지 입니다... 😭
🚀 CODE
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
static double[][] dp;
static StringBuilder res=new StringBuilder();
private 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 void getResult(int a,int z,double k){
if(a==0){
for(int i=0;i<z;i++)
res.append("z");
return;
}
if(z==0){
for(int i=0;i<a;i++)
res.append("a");
return;
}
double check = check(a - 1, z);
if(k>check){
res.append("z");
getResult(a,z-1,k-check);
}
else{
res.append("a");
getResult(a-1,z,k);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine()," ");
int n,m;
double k;
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
k=Integer.parseInt(st.nextToken());
dp=new double[n+1][m+1];
getResult(n,m,k);
if(check(n,m)<k)
System.out.println(-1);
else
System.out.println(res.toString());
}
}
👏 정답
😍 이상으로 포스팅을 마치겠습니다. 감사합니다 :)
