글 읽기 - 단어수학 시간초과 질문 있습니다.

kcm5680 8년 전 0

backtracking으로 순열로 각 알파벳마다 숫자를 적용하여 전수 계산하니 시간 초과가 나오네요 ;;;

ㅠㅠ 아래 소스좀 봐주세요 고수님들

#include <iostream>
#include <cstdlib>
using namespace std;

typedef struct word
{
	int num;
	char charteristics;
}WORD;

typedef struct cal
{
	char ori_word[10];
	char changed_num[10];
	int pos;
}CAL;

WORD word[10];
CAL ori[10];
int visit[10] = { 0, };
int N, index;
int max1;

void cal_word(int n);

int main()
{
	
	freopen("word.txt", "r", stdin);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> ori[i].ori_word;
	}

	index = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; ; j++)
		{
			if (ori[i].ori_word[j] == '\0')
			{
				ori[i].pos = j;
				break;
			}
				
			int flag = 1;
			for (int k = 0; k < 10; k++)
			{
				if (word[k].charteristics == ori[i].ori_word[j])
				{
					flag = 0;
					break;
				}
			}

			if (flag == 1)
			{
				word[index].charteristics = ori[i].ori_word[j];
				index++;
			}
		}
	}
	
	cal_word(0);

	cout << max1 << endl;
	
}


void cal_word(int n)
{
	
	if (n == index)
	{
		int temp = 0;
		
		for (int i = 0; i < N; i++)
		{
			for (int j = 0;; j++)
			{
				if (ori[i].ori_word[j] == '\0')
				{
					break;
				}

				for (int k = 0; k < index; k++)
				{
					if (ori[i].ori_word[j] == word[k].charteristics)
					{
						ori[i].changed_num[j] = word[k].num + 48;
					}
				}
			}

			temp += atoi(ori[i].changed_num); 
		}

		if (max1 < temp)
			max1 = temp;
		
		return;
	}

	for (int i = 9; i > 9-index; i--)
	{
		if (visit[i] == 0)
		{
			visit[i] = 1;
			word[n].num = i;
			cal_word(n + 1);
			visit[i] = 0;
		}
	}
}

indioindio 8년 전 0

ABC DDD의 덧셈을 직접 손으로 해보시면 도움이 될 것 같습니다.

kcm5680 8년 전 0

999 + 876일텐데.. 뭐 간단한 경우 말고 전수 조사를 다 해봐야 하지 않을까요??

indioindio 8년 전 2

그냥 다항식 더하듯이 덧셈을 해보시라는 뜻이었습니다. 일례로 AB + B가 있다면 10*A + 2*B가 되겠죠.

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

문제

문제

출처

ICPC

단어수학 시간초과 질문 있습니다.

kcm5680 8년 전 0

indioindio 8년 전 0

kcm5680 8년 전 0

indioindio 8년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말