문제 설명
간단한 설명
문자열 맨 처음 알파벳부터 인덱스를 1,2,3...이라 매겼을 때 각 알파벳이 맨 처음 등장한 인덱스만큼 문자열에서 그 문자가 등장하는 것을 Ideal String이라 함
ex)
BAOOOA는 Ideal String이다
- B는 맨 처음 등장한 인덱스가 1이고, 문자열에 한번 등장함
- A는 맨 처음 등장한 인덱스가 2이고, 문자열에 두번 등장함
- O는 맨 처음 등장한 인덱스가 3이고, 문자열에 세번 등장함
위의 규칙을 따르는 길이가 N인 가장 빠른 Ideal String을 찾는 것이 문제
불가능하다면 -1을 출력
해결 방법
우선 예제에 보면 -1이 나오는 경우가 생기게 되는데 이에 대하여 생각해보겠다
ㅡ
길이가 1인 Ideal String
맨 앞자리에 알파벳 하나가 오고 이 알파벳은 인덱스 1인것에 맞게 한번 등장했으므로 Ideal String 이 성립
따라서 존재할 수 있게 됨
ㅡ ㅡ
길이가 2인 Ideal String
맨 앞자리는 위와 같은 이유로 성립되지만 한칸 뒤의 문자가 두번 등장해야 하는데 한번만 등장하므로 성립할 수 없음
따라서 두번째 문자가 이 뒤에 등장하면 길이가 3인 Ideal String은 존재할 수 있게 됨
규칙성을 찾기 위해 정답이 될 수 있는 배열을 순서대로 만들어 보았다
1은 A, 2는 B라 가정하면 됨
이것으로는 백트래킹을 사용할 수 없음,,,
이 그림에서 줄그어 놓은 부분
즉, 각 알파벳이 처음으로 등장하는 위치를 다시 나열해보았다 (오른쪽)
이 수열은 백트래킹 사용이 가능해보인다
해석하자면 맨 첫줄은 첫번째 자리 A
두번째 줄은 첫번째 자리 A, 두번째 자리 B...
이런식으로 표현만 해도 되는 이유는 만약 네번째 줄 1 2 4를 해석하면
AB_C인데
이렇게 가지는 가장 빠른 Ideal String은 무조건 ABBCCC가 되기 때문
여기서 찾을 수 있는 규칙성은 각 자리의 최대값은 앞자리 위치의 합+1 보다 작아야 한다 는 것이다
다시 설명하면 위의 1 2 4 8은
AB_C___D를 뜻하는데 (다 만들면 ABBCCCCDDDDDDDD)
만약 D의 위치가 9, 즉 배열이 1 2 4 9가 된다면
A B C 각각 1 2 4번 등장하고 총 합하면 7개의 알파벳이 등장,
D의 앞에 한자리를 채울 수 없게 된다...
따라서 네번째 자리는 1 + 2 + 4 +1 보다 작거나 같음을 만족해야한다
다른 자리도 마찬가지
C가 맨 처음으로 5번째 위치에 오게 된다면
앞의 A,B가 어느 위치에 오든 4칸을 채울 수 없음
정리하면
1. 각 알파벳이 가장 먼저 나오는 자리를 조건에 맞게 백트래킹으로 찾아준다
2. 이 자리에 맞는 수만큼 앞에서부터 알파벳을 채워준다
코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int alpha[27]; // 'A'의 맨 처음 등장 위치는 alpha[1].
char result[101];
int ans[27];
int num;
int check=0;
void print_result(int len){
for(int i=1;i<=len;i++){
if(result[i]==0){
printf("0");
}else{
printf("%c",result[i]);
}
}
printf("\n");
}
void back(int len, int pos,int sum){
if(len+1==pos){
if(sum==num){
check =1;
memcpy(ans, alpha, sizeof(alpha));
}
// for(int i=1;i<=len;i++){
// printf("%d ",alpha[i]);
// }
// printf("\n");
}else{
for(int i=alpha[pos-1]+1;i<=sum+1;i++){
if(sum+i>num){
break;
}
alpha[pos] = i;
back(len,pos+1,sum+i);
}
}
}
int main(){
scanf("%d",&num);
for(int i=1;i<18;i++){
back(i,1,0);
if(check==1){
for(int j=1;j<=i;j++){
result[ans[j]] = 'A'+j-1;
}
int cnt = 1;
for(int j=1;j<=i;j++){
while(ans[j]!=1){
if(result[cnt]==0){
result[cnt]='A'+j-1;
ans[j]--;
cnt++;
}else{
cnt++;
}
}
}
for(int j=1;j<=num;j++){
if(result[j]==0){
printf("0");
}else{
printf("%c",result[j]);
}
}
exit(0);
}
}
printf("-1");
}