출처: https://www.acmicpc.net/problem/1271
문제
- 프로토스 중앙 우주 정부의 정책인, ‘모든 지적 생명체는 동등하다’라는 규칙에 입각해서 돈을 똑같이 분배하고자 한다.한 생명체에게 얼마씩 돈을 줄 수 있는가?
조건
- 첫째 줄에는 최백준 조교가 가진 돈 n과 돈을 받으러 온 생명체의 수 m이 주어진다. (1 ≤ m ≤ n ≤ 10^1000, m과 n은 10진수 정수)
SOL
조건이 아주아주 사악한 문제 중 하나이다. longlong 범위를 뛰어넘는 큰 수를 처리할 때, 어떻게 할 것이냐!가 문제이다.
실생활에서 와닿게 하기 위해서, 이런 범위가 매우매우 중요한 "돈"과 관련된 시스템이라고 생각해보자. int의 범위는 21억밖에 안되니까, 만약 통장잔고를 int로 표현한다면, 여러분의 돈은 21억이 최대일것이다. 서울에 집 못산다.
Int64는 9,223,372,036,854,775,807로, 9천"경"에 해당한다. 우리나라 예산이 650조라고 하니까..흠 그만 알아보자. 미국이라면, 저 정도의 돈의 흐름이 생길까? 싶긴하지만 진짜 웬만하면 다 int64안에서 해결이 가능할것 같은 느낌이다.
일단 ,10^1000과같은 어마어마한 수는 , 혹은 예전에 메모리가 부족했던 시절에는 정수를 문자열로 표현해서 계산을 하였다고 한다. 위와 같은 문제를 C++로 푼다면 문자열로 바꿔서 계산하는 과정이 필수이다.
문자열로 사칙연산을 하는 것도 한번 다루어 봐야겠다.
#include <iostream>
#include <cstring>
using namespace std;
char *big(char *a, char *b)
{
for (int i = 0; i < strlen(a); i++)
{
if (a[i] < b[i])
return b;
if (a[i] > b[i])
return a;
}
return a;
}
void subtract(char *a, char *b)// 나눗셈은 뺄셈을 여러번하는 연산이다.
{
for (int i = 0; i < strlen(b); i++)
{
a[i] = a[i] - b[i] + '0';
}
for (int i = strlen(b) - 1; i >= 0; i--)
{
if (a[i] < '0')
{
a[i] += 10;
a[i - 1]--;
}
}
}
void devidesubtract(char *a, char *b, char *q, int index)
{
q[index] = '0';
while (a[index - 1] > '0' || big(a + index, b) == a + index)
{
subtract(a + index, b);
++q[index];
}
}
void devide(char *a, char *b, char *q)
{
int index = 0;
int digit = strlen(a) - strlen(b);
while (index <= digit)
devidesubtract(a, b, q, index++);
q[index] = '\0';
}
int main()
{
char a[1001];
char b[1001];
char q[1001];
int qi = 0, ai = 0;
cin >> a >> b;
devide(a, b, q);
while (q[qi] == '0')
qi++;
while (a[ai] == '0')
ai++;
if (q[0] == '\0')
{
q[0] = '0';
q[1] = '\0';
}
if (a[ai] == '\0')
ai--;
if (q[qi] == '\0')
qi--;
cout << q + qi << '\n';
cout << a + ai << '\n';
return 0;
}- C++에서 문자열의 시작주소를 cout하면, 문자열부터 문자열이 끝날 때까지, 다 출력해줌.
- 문자열의 시작주소 +1,문자열의 시작주소 +2 ..와 같이 할 수도 있음. max함수는 비교할 때, 앞자리를 비교하는 이유가 나눗셈을 할 때, 앞자리가 크면, 다음자리로 내려가야하기 때문임.
