글 읽기 - 1352 문자열 문제 도와주세요.

sehun 8년 전 0

안녕하세요!

1352 문제를 제가 파악을 잘 못 한 것인지, 검증할 데이터도 만들기 어렵고..

질문드립니다.

아래처럼 출력하면 되는게 아닌가요.ㅜㅜ

[sehun@eileen study]$ ./a.out
6
ABCBCC

[sehun@eileen study]$ ./a.out
10
ABCDBCCDDD

[sehun@eileen study]$ ./a.out
16
ABCDDEBCCDDEEEEE

[sehun@eileen study]$ ./a.out
100
ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEEFFFFFGFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG

[sehun@eileen study]$ ./a.out
8
-1

[sehun@eileen study]$

#include <stdio.h>
#define MUST_HAVE 0
#define NOW_HAVE 1

int N=0;
char found=0;

int need_digits(int map[26][2]){
	int i,sumneed;
	sumneed=0;
	for(i=0;i<26;i++){
		sumneed+= map[i][MUST_HAVE] - map[i][NOW_HAVE];
	}
	return sumneed;
}

void F(int n, char str[], int map[26][2]){
	if(found==1){ //if already answer comes out!
		return;
	}
	//printf("F: %s\n", str);
	if(n==N){ //now check if it's an ideal string!
		int i=0;
		for(i=0;i<26;i++){
			if(map[i][MUST_HAVE] != map[i][NOW_HAVE]){
				break;
			}
		}
		if(i==26){
			found=1;
			printf("%s\n", str);
		}
	}
	//no answer condition : no need to compute more.
	if(N-n < need_digits(map)){
		return;
	}
	//we still have works
	if(n+1<=N){
		char c=0;
		for(c='A';c<=str[n-1]+1;c++){

			if(map[c-'A'][MUST_HAVE] ==0 || map[c-'A'][NOW_HAVE] < map[c-'A'][MUST_HAVE]){
				char tmp_now_have = map[c-'A'][NOW_HAVE];
				char tmp_must_have = map[c-'A'][MUST_HAVE];
				str[n] = c;
				map[c-'A'][NOW_HAVE]++;
				if(map[c-'A'][MUST_HAVE] ==0){
					map[c-'A'][MUST_HAVE] = n+1;
				}
				F(n+1,str,map);
				str[n] = 0;
				map[c-'A'][NOW_HAVE] = tmp_now_have;
				map[c-'A'][MUST_HAVE] = tmp_must_have;
			}

		}//for
	}//if

}

int main(){
	char str[101]={0,};
	int map[26][2]={0,}; //assume like :0='A', 1='B', 2='C', ...25='Z'

	scanf("%d", &N);
	//set string 'A' at startup.
	str[0] = 'A';
	map[0][MUST_HAVE] = 1;
	map[0][NOW_HAVE] = 1; 

	//go!
	F(1,str, map);

	if(found==0){
		printf("-1\n");
	}
	return 0;
}

algospot 8년 전 1

먼저 문제점은 dfs() 내부의 for문 안에 'A'~str[n-1]+1 까지에서 str[n-1]+1 이 문제가 됩니다.

질문자께서 str[n-1]+1까지 한 이유는 사전순 빠를려면 다음문자가 최대한 작은게 와야하고, 'A'~그전문자까지 중 덜 완성된게 있다면 그걸쓰고 아니면 new character를 쓰게 되는데 new character를 쓰게 된다면 모두 같은 상황이니 가장 작은 걸 쓰는 것을 목표로 두고 설정한 거 같습니다.

비슷한 논리지만, 오류가 있습니다.

'A'~str[n-1]중에 가장 큰 문자가 str[n-1]이 아닐수도 있습니다. 즉, for 문들어가기전에

str[0]~str[n-1]중 가장 큰 문자열을 찾은뒤 그 문자열+1 까지 조사하면 되겠습니다.

하지만 그걸 고친다면 오답은 면할수있지만, 64~80의 분포에 대한 시간초과를 면할 순 없어서 그걸 생각 해 보시면 될거 같습니다.

sehun 8년 전 0

정말로, 정말로, 답변 감사드립니다!

이런 오류가 있는지도 몰랐습니다.

이제 시간초과를 해결해 봐야 겠습니다.!

algospot 8년 전 0

sehun님께 도움을 줄 수 있어서 저도 기분이 좋네요~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1352 문자열 문제 도와주세요.

sehun 8년 전 0

algospot 8년 전 1

sehun 8년 전 0

algospot 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말