글 읽기 - 나눗셈의 몫을 구할 때 시간 초과가 나오는 것 같습니다..

seonjoo2030 1년 전 0

나머지가 빼기의 연속이라는 것을 생각해서 코딩을 해봤습니다.

시간 초과 에러가 발생하는데, 제가 임의로 큰 숫자를 돌려봐도 오래 걸리긴 하더라구요...

몫을 구하는 알고리즘을 좀 더 단순하고 빠르게 하는 방법이 있는건지 잘 모르겠습니다.

getQuotient 함수가 뺄셈을 할 때 마다 1씩 더해주는 함수입니다.

또한 두 숫자 중에 큰 숫자를 확인하는 함수가 Max 함수인데,

해당 함수를 좀 더 편하게 사용하기 위해

숫자의 자릿수를 맞추는 부분이 있습니다.

123과 20을 비교할 경우, 20을 020 이렇게 앞에 0을 채우고 있습니다.

혹시 이 방법도 다른 방법이 있을지 궁금합니다...

해당 부분은 아래와 같습니다.

for (int i = iSecNumLen - 1; i >= 0; i--)
{
szTemp[iFirstNumLen - 1] = szTemp[iFirstNumLen - 1] + pszSecNum[i] - '0';
iFirstNumLen--;
}

#include <stdio.h>
#include <string.h>


int getQuotient(char* pszQuotient, int iQuotientLen)
{
	pszQuotient[iQuotientLen - 1] = pszQuotient[iQuotientLen - 1] + 1;
	if ('9' < pszQuotient[iQuotientLen - 1])
	{
		while ('9' < pszQuotient[iQuotientLen - 1])
		{
			pszQuotient[iQuotientLen - 1] = '0';
			pszQuotient[iQuotientLen - 1 - 1] = pszQuotient[iQuotientLen - 1 - 1] + 1;
			iQuotientLen--;
		}
	}

	return 0;
}

char* Max(char* pszFirstNum, char* pszSecNum)
{
	int iFirstNumLen = 0;
	int iSecNumLen = 0;

	iFirstNumLen = strlen(pszFirstNum);
	iSecNumLen = strlen(pszSecNum);

	if (iSecNumLen < iFirstNumLen)
		return pszFirstNum;
	else if (iSecNumLen > iFirstNumLen)
		return pszSecNum;
	else
	{
		for (int i = 0; i < iFirstNumLen; i++)
		{
			if (pszFirstNum[i] > pszSecNum[i])
				return pszFirstNum;
			else if (pszFirstNum[i] < pszSecNum[i])
				return pszSecNum;
		}
	}
	return pszFirstNum;
}

int Subtract(char* pszFirstNum, char* pszSecNum)
{
	int iFirstNumLen = 0;
	int iSecNumLen = 0;
	int iUpper = 0;
	if (NULL == pszFirstNum || NULL == pszSecNum)
		return -1;

	iFirstNumLen = strlen(pszFirstNum);
	iSecNumLen = strlen(pszSecNum);

	for (int i = iSecNumLen - 1; i >= 0; i--)
	{
		pszFirstNum[iFirstNumLen - 1] = pszFirstNum[iFirstNumLen - 1] - pszSecNum[i] - iUpper + '0';
		if ('0' > pszFirstNum[iFirstNumLen - 1])
		{
			pszFirstNum[iFirstNumLen - 1] = pszFirstNum[iFirstNumLen - 1] + 10;
			iUpper = 1;
		}
		else
		{
			iUpper = 0;
		}
		iFirstNumLen--;
	}
	
	if (iUpper)
		pszFirstNum[iFirstNumLen - 1] = pszFirstNum[iFirstNumLen - 1] - 1;

	return 0;
}

int Devide(char* pszFirstNum, char* pszSecNum, char* pszQuotient)
{
	int iFirstNumLen = 0;
	int iSecNumLen = 0;
	int iQuotientLen = 0;
	char szTemp[1001] = { 0 };

	iFirstNumLen = strlen(pszFirstNum);
	iSecNumLen = strlen(pszSecNum);

	iQuotientLen = iFirstNumLen - iSecNumLen + 1;

	for (int i = 0; i < iQuotientLen; i++)
	{
		pszQuotient[i] = '0';
	}

	pszQuotient[iQuotientLen] = '\0';

	memset(szTemp, '0', iFirstNumLen);

	for (int i = iSecNumLen - 1; i >= 0; i--)
	{
		szTemp[iFirstNumLen - 1] = szTemp[iFirstNumLen - 1] + pszSecNum[i] - '0';
		iFirstNumLen--;
	}

	while (Max(pszFirstNum, szTemp) == pszFirstNum)
	{
		Subtract(pszFirstNum, szTemp);
		getQuotient(pszQuotient, iQuotientLen);
	}

	return 0;
}

int main()
{
	char szMoney[1001] = { 0 };
	char szNum[1001] = { 0 };
	char szQuotient[1001] = { 0 };
	int iIndex = 0;
	int iQindex = 0;

	scanf("%s %s", szMoney, szNum);

	if (!strcmp(szMoney, szNum))
		printf("1\n0\n");
	else if (!strcmp(szNum, "1"))
		printf("%s\n0\n", szMoney);
	else
	{
		Devide(szMoney, szNum, szQuotient);

		while ('0' == szMoney[iIndex])
			iIndex++;

		if ('\0' == szMoney[iIndex])
			iIndex--;

		while ('0' == szQuotient[iQindex])
			iQindex++;

		if ('\0' == szQuotient[iQindex])
			iQindex--;


		printf("%s\n%s\n", szQuotient + iQindex, szMoney + iIndex);
	}

	return 0;
}

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

문제

문제

출처

ICPC

나눗셈의 몫을 구할 때 시간 초과가 나오는 것 같습니다..

seonjoo2030 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말