https://www.acmicpc.net/problem/1256

제출결과

이번문제는 제출 결과부터 ^^..

#1

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,m;
ll k;
vector<string> dict;

void solve(int depth,int a, int z, string tmp){
	if(a<0 || z<0 || depth == n+m){
		if(tmp.size() == n+m && a>=0 && z>=0) dict.push_back(tmp);
		tmp="";
		return;
	}
	
	solve(depth+1, a-1, z, tmp+"a");
	solve(depth+1, a, z-1, tmp+"z");
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin>>n>>m>>k;
	
	solve(0,n,m,"");
	
	if(dict.size()<k) cout<<-1;
	else cout<<dict[k-1];
}

정말 단순히 백트래킹 하면 되겠거니 하고 풀었다.

주어진 테스트 케이스 통과했으니까 냅다 제출했음
하지만 결과는 메모리초과 ^.ㅜ so sad

#2

조합으로 풀어보자

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

ll n,m,k;
ll dp[201][201];
string ans;

void comb(){
	for(int i = 1; i<=200; i++){
		for(int j = 0; j<=200; j++){
			if(j==0 || i==j) {dp[i][j] = 1; continue;}
			ll val = dp[i-1][j-1] + dp[i-1][j];
			if(val>1e9) dp[i][j] = INF;
			else dp[i][j] = val;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin>>n>>m>>k;
	
	comb();
	
	ll size = n+m;
	if(dp[size][m]<k) cout<<-1;
	else{
		while(ans.size()<size){
			if(!n || !m){
				while(n--) ans += "a";
				while(m--) ans += "z";
				break;
			}
			if(k<=dp[n+m-1][m]){
				ans += "a";
				n--;
			}
			else{
				k -= dp[n+m-1][m];
				ans += "z";
				m--;
			}	
			}
		}
		cout<<ans<<"\n";
		cout<<ans.size()<<"\n";
	}

• 주어진 $k$가 만들어지는 단어의 전체 개수인 ${n+m\choose m}$보다 크다면, -1를 출력하면 된다.
  $a$ : $n$개, $z$ : $m$개로 만들어지는 단어의 길이는 $n+m$이다.
  이 때 만들 수 있는 단어의 경우의 수는
  $n+m$에서 $z$가 들어갈 자리 $m$개를 선택하는 경우와 같으므로, ${n+m\choose m}$과 같다.
• 그렇다면, 단어는 어떻게 만드는가?
  같은 자리라면 $a$는 $z$보다 무조건 앞 순서이다.
  무슨뜻이냐면 $a$xxxxx 는 $z$xxxxx보다 항상 앞선다는 말이다.
  
  앞을 $a$로 고정시키고 생각해보면, $z$로 시작하는 문자는 $a$로 시작하는 문자의 모든 경우의 수 다음에야 올 수 있다는 것을 볼 수 있다.
  그러면, $a$로 시작하는 문자의 모든 경우의 수는?
  맨 앞 $a$의 자리가 고정되었으므로 남은 자리는 $n+m-1$자리이다.
  남은 자리 중에서 $z$가 올 수 있는 자리 $m$개를 선택하면 된다.
  ($z$자리가 결정되면 자동으로 $a$자리는 확정이니까 그게 그거다) $\ \therefore {m+n-1\choose m}$
  이 때!
  만약 $k$가 ${m+n-1\choose m}$보다 작다면 $a$로 시작하는 문자일 것이다.
  그렇지 않다면, $z$로 시작하는 문자열인 것이다.
• 첫 단어 결정, 그 다음은?
  $a$로 결정되었다면 계속 $k$번째 단어를 찾아나가면 된다.
  하지만 $z$라면, "우리가 찾는 단어는 $z$로 시작하는 단어 중에 몇 번째인가"를 고려해야한다. 이는 ${m+n-1\choose m}$ 이후 $x$번째 이므로, $k$에서 ${m+n-1\choose m}$를 빼준다면 알 수 있다.
• 문자가 고갈되었어요
  찾다가 보면 $a$를 다 썼을 수도 있고, $z$를 다 썼을 수도 있다.
  남은 개수만큼 $a$ 아니면 $z$를 출력해주고, 끝내면 된다.
  아무튼 $a$먼저니까 $a$ 출력하는걸 먼저 쓰긴 했음

#3

그렇지만 틀렸다 !
문제는 조합을 구하는 데 있었다.
문자열 최대 길이가 200이므로,
.. dp 채우는 과정에서 $_{200}C_{어쩌구}$를 구할 때면 매우 큰 숫자가 나오기 때문,,, ㅠㅠ
long long 도 초과한다고 한다.

$k$는 $10^9$까지이므로,
오버플로우를 막기 위해 계산 결과가 $10^9$이 넘어가면, 적당히 큰 수로 채워주도록 했다.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

ll n,m,k;
ll dp[201][201];
string ans;

void comb(){
	for(int i = 1; i<=200; i++){
		for(int j = 0; j<=200; j++){
			if(j==0 || i==j) {dp[i][j] = 1; continue;}
			ll val = dp[i-1][j-1] + dp[i-1][j];
			if(val>1e9) dp[i][j] = INF;
			else dp[i][j] = val;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin>>n>>m>>k;
	
	comb();
	
	ll size = n+m;
	if(dp[size][m]<k) cout<<-1;
	else{
		while(ans.size()<size){
			if(!n || !m){
				while(n--) ans += "a";
				while(m--) ans += "z";
				break;
			}
			if(k<=dp[n+m-1][m]){
				ans += "a";
				n--;
			}
			else{
				k -= dp[n+m-1][m];
				ans += "z";
				m--;
			}	
			}
		}
		cout<<ans<<"\n";
	}

겨우 맞았지만 너무 어렵당