https://www.acmicpc.net/problem/1256
이번문제는 제출 결과부터 ^^..
#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
조합으로 풀어보자
#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";
}
그렇지만 틀렸다 !
문제는 조합을 구하는 데 있었다.
문자열 최대 길이가 200이므로,
.. dp 채우는 과정에서 를 구할 때면 매우 큰 숫자가 나오기 때문,,, ㅠㅠ
long long
도 초과한다고 한다.
는 까지이므로,
오버플로우를 막기 위해 계산 결과가 이 넘어가면, 적당히 큰 수로 채워주도록 했다.
#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";
}
겨우 맞았지만 너무 어렵당