[백준 문제 C++] 엄청난 부자2

https://www.acmicpc.net/problem/1271

1271번: 엄청난 부자2

n / m 의 몫과 나머지를 출력하면 되는 문제.

 

처음에 별거 아니잖아? 하고 덤벼들었는데 1 ~ 10^1000 범위의 숫자에 대한 연산이 필요한 문제였습니다.

입력 값이 1001 "자리" 가 나온다는 의미입니다.  ("천억" 의 자리는 0000,0000,0000 12자리밖에 되지 않네요.)

 

풀이에 떠올린 아이디어는 이렇습니다.

우선 입력은 문자열로 받고 계산하기 편하게 숫자 배열로 만들어줍니다.

그리고 뺄셈을 통해 몫과 나머지를 구해줄 겁니다.

 

먼저 우리가 나누기를 진행할 때를 기억해보면

483216 / 30

 

        1 

    ㅡㅡㅡㅡㅡㅡ 

30) 4 8 3 2 1 6

     3 0

    ㅡㅡㅡㅡㅡㅡ

     1 8 3

 

        1 6

    ㅡㅡㅡㅡㅡㅡ 

30) 4 8 3 2 1 6

     3 0

    ㅡㅡㅡㅡㅡㅡ

     1 8 3

     1 8 0

    ㅡㅡㅡㅡㅡㅡ

          3 2

          .....

 

이런식으로 진행이 됩니다.

이 과정을 컴퓨터에게 시키면 몫과 나머지를 구할 수 있습니다.

대신 앞에서부터 뺄셈을 진행할 것이기 때문에 뺄셈이 진행되는 도중 불가능한 것이 판명되면

뺀 숫자들을 다시 더해주고 복구시켜 주겠습니다.

 

ex)

  574 / 575 진행 시

  574

- 5

ㅡㅡㅡ

    74

-   7

ㅡㅡㅡ

      4

-     5

 (진행이 불가능 하므로 앞의 57을 복구시켜 줘야됩니다.)

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> moneyArray;
vector<int> personsArray;

int moneyLength;
int personsLength;

void MakeIntArray(vector<int>& arr, string& str, int length)
{
	for (int i = 0; i < length; ++i)
	{
		arr[i] = str[i] - '0';
	}
}

void PrintQuotient(vector<int>& quotient)
{
	int size = quotient.size();

	if (size == 0) //몫이 없는 경우
	{
		cout << 0;
		return;
	}

	for (int i = 0; i < size; ++i)
	{
		cout << quotient[i];
	}
}

void PrintRemainder()
{
	int i = 0;

	while (i < moneyLength && moneyArray[i] == 0)
	{
		i++;
	}

	if (i < moneyLength) //나머지가 있는 경우
	{
		while (i < moneyLength)
		{
			cout << moneyArray[i];
			i++;
		}
	}
	else //나머지가 없는 경우
	{
		cout << 0;
	}

	cout << endl;
}

int Subtraction(int base)
{
	int index = base - personsLength + 1;
	//47664
	//46669
	//현재 base = 4, personsLength = 5로
	//index = 0 이 됩니다. 비교할 첫 시작점을 의미합니다.

	for (int i = 0; i < personsLength; ++i)
	{
		if (moneyArray[index + i] - personsArray[i] < 0) //앞에서 자리를 빌려와야됨
		{
			int j = 1;

			//47664
			//46669
			//0100 <4 - 9>
			//위 부분에서 앞자리에 빌려올 곳을 찾아야됩니다.
			while (index + i - j >= index && moneyArray[index + i - j] == 0)
			{
				j++;
			}

			if (index + i - j < index) //빌려올 곳이 시작지점을 넘어서면 못빌려옵니다.
			{
				return i; //뺄셈이 불가능하기에 빼준 앞 부분들까지 다시 더해주기 위해
						  //인덱스를 반환합니다.
			}

			moneyArray[index + i - j]--; //요기서 빌릴 수 있네요.
			j--;
			while (j > 0)
			{
				moneyArray[index + i - j] = 9; //빌려오면서 거친 부분들은 9로 만들어줍니다.
				j--;
			}
			//0100 -> 0099 가 됩니다.

			moneyArray[index + i] += 10 - personsArray[i]; //0099(14 - 9) = 00995
		}
		else //뺄셈이 가능하면 그냥 빼주기
		{
			moneyArray[index + i] -= personsArray[i];
		}
	}

	return -1; //뺄셈이 성공하면 다시 더해줄 필요가 없음
}

void Sum(int base, int limit) //뺄셈이 실패하기 - 1 지점까지 다시 더해서 복구해주기
{
	int index = base - personsLength + 1;

	for (int i = limit - 1; i >= 0; --i)
	{
		moneyArray[index + i] += personsArray[i];
	}
}

int main()
{
	string money, persons;
	vector<int> quotient;

	cin >> money >> persons;

	moneyLength = money.length();
	personsLength = persons.length();

	moneyArray.resize(moneyLength);
	personsArray.resize(personsLength);

	MakeIntArray(moneyArray, money, moneyLength);
	MakeIntArray(personsArray, persons, personsLength);

	for (int i = personsLength - 1; i < moneyLength; ++i)
	{
		//만약 1234 / 124의 경우
		//123 / 124 는 실패합니다.
		//이제 234 / 124 비교 차례인데
		//앞의 숫자(1)가 남아있는걸 갖고와주는 작업입니다.
		if (i - personsLength >= 0)
		{
			moneyArray[i - personsLength + 1] += moneyArray[i - personsLength] * 10;
			moneyArray[i - personsLength] = 0;
		}

		int div = 0; //몫

		while (true)
		{
			int failPos = Subtraction(i); //빼질때까지 계속 빼보기

			if (failPos > -1) //더이상 나눌수(뺄 수) 없으면 복구해주고 종료.
			{
				Sum(i, failPos);
				break;
			}

			div++;
		}

		if (quotient.size() == 0 && div == 0) //첫 몫이 0인지 확인
		{
			continue;
		}
		else
		{
			quotient.push_back(div);
		}
	}

	PrintQuotient(quotient);
	cout << " ";
	PrintRemainder();
}