글 읽기 - 0ms 나오신 분들은 어떻게 구현하셨나요?

juhongkim2 6년 전 0

저같은 경우엔 딱히 해결방안이 떠오르지 않아서

입력받은 알파벳들을 alphabet배열에 중복없이 넣어준 다음 오름차순 정렬해서

alphabet배열로 가능한 모든 경우의 순열을 만들고 각각의 경우에 9부터 값을 줄여나가며 알파벳마다

값을 할당해주고 합을 구해서 최대값을 구해줬습니다.

오래 걸릴거라곤 예상했는데

1000ms넘어가니 풀어도 푼거같지가 않네요...

0ms나오시거나 0ms아니라도 빠르게 나오신분들

어떤 아이디어로 구현했는지 조언 부탁드립니다.

맞으신 분들 코드를 몇개 훑어 봤는데

어떤식으로 생각하신건지를 잘 모르겠어서...

#include <stdio.h>

char num[20][10],alphabet[10],per[10];
int N,ans,val[30],check[30],pcheck[30];

int Max(int n1, int n2)
{
	if(n1>n2)
		return n1;

	return n2;
}

int Inv(int n)
{
	int i,res=1;

	for(i=1;i<=n;i++){
		res*=10;
	}

	return res;
}

int Calc()
{
	int i,j,len,res=0;

	for(i=0;i<N;i++){
		len=-1;
		while(num[i][++len]);

		for(j=0;j<len;j++){
			res+=val[num[i][j]-'A']*Inv(len-j-1);
		}
	}

	return res;
}

void Quick(int left, int right)
{
	int l,r;
	char pivot,tmp;

	if(left<right){
		l=left-1;
		r=right+1;
		pivot=alphabet[(left+right)/2];

		while(1){
			while(alphabet[++l]<pivot);
			while(alphabet[--r]>pivot);

			if(l>=r)
				break;

			tmp=alphabet[l];
			alphabet[l]=alphabet[r];
			alphabet[r]=tmp;
		}

		Quick(left,l-1);
		Quick(r+1,right);
	}
}

void Permutation(int dep, int len)
{
	int i,v;

	if(dep>len){
		for(i=1,v=9;i<=len;i++,v--){
			val[per[i]-'A']=v;
		}

		ans=Max(ans,Calc());

		return;
	}

	for(i=0;i<len;i++){
		if(pcheck[alphabet[i]-'A']==0){
			pcheck[alphabet[i]-'A']=1;
			per[dep]=alphabet[i];
			Permutation(dep+1,len);
			pcheck[alphabet[i]-'A']=0;
		}
	}
}

int main()
{
	int i,j,len,idx=0;

	scanf("%d",&N);

	for(i=0;i<N;i++){
		scanf(" %s", num[i]);

		len=-1;
		while(num[i][++len]);

		for(j=0;j<len;j++){
			if(check[num[i][j]-'A']==0){
				alphabet[idx++]=num[i][j];
				check[num[i][j]-'A']=1;
			}
		}
	}
	Quick(0,idx-1);

	Permutation(1,idx);

	printf("%d\n",ans);

	return 0;
}

doju 6년 전 2

단어를 각 알파벳을 미지수로 갖는 다항식으로 생각해 보세요.
ex. ABC = 100A + 10B + C

juhongkim2 6년 전 0

답변 감사합니다.

Calc()함수부분 그렇게 짠다고 짜본건데 다른방법이 있나보군요...

갈길이 머네요..

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

문제

문제

출처

ICPC

0ms 나오신 분들은 어떻게 구현하셨나요?

juhongkim2 6년 전 0

doju 6년 전 2

juhongkim2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말