[C] 1271번: 엄청난 부자2
[C] 1271번: 엄청난 부자2
문제
https://www.acmicpc.net/problem/1271
갑부 최백준 조교는 동전을 최소로 바꾸는데 성공했으나 김재홍 조교가 그 돈을 발견해서 최백준 조교에게 그 돈을 나누자고 따진다.
그 사실이 전 우주로 알려지자 우주에 있던 많은 생명체들이 자신들에게 돈을 분배해 달라고 당장 달려오기 시작했다.
프로토스 중앙 우주 정부의 정책인, ‘모든 지적 생명체는 동등하다’라는 규칙에 입각해서 돈을 똑같이 분배하고자 한다.
한 생명체에게 얼마씩 돈을 줄 수 있는가?
또, 생명체들에게 동일하게 분배한 후 남는 돈은 얼마인가?
입력
첫째 줄에는 최백준 조교가 가진 돈 n과 돈을 받으러 온 생명체의 수 m이 주어진다. (1 ≤ m ≤ n ≤ 101000, m과 n은 10진수 정수)
출력
첫째 줄에 생명체 하나에게 돌아가는 돈의 양을 출력한다. 그리고 두 번째 줄에는 1원씩 분배할 수 없는 남는 돈을 출력한다.
풀이
입력 범위가 매우 커서 일반 정수형으로 처리할 수 없습니다.
C에는 자바의 BigInteger 같은 기능이 없으므로, 문자열로 큰 수를 입력받아 긴 나눗셈을 직접 구현해야 합니다.
왼쪽부터 한 자리씩 내려오면서 현재 값을 만들고, 그 값에서 divisor를 뺄 수 있을 만큼 빼서 몫의 각 자릿수를 구하면 됩니다.
코드
#include <stdio.h>#include <string.h>
#define MAX 1001
void normalize(const char *src, char *dst) { int i = 0; while (src[i] == '0' && src[i + 1] != '\0') { i++; } strcpy(dst, src + i);}
int compare_num(const char *a, const char *b) { int len_a = strlen(a); int len_b = strlen(b);
if (len_a > len_b) return 1; if (len_a < len_b) return -1;
int cmp = strcmp(a, b); if (cmp > 0) return 1; if (cmp < 0) return -1; return 0;}
void subtract_num(const char *a, const char *b, char *result) { char temp[MAX]; int len_a = strlen(a); int len_b = strlen(b); int i = len_a - 1; int j = len_b - 1; int k = 0; int borrow = 0;
while (i >= 0 || j >= 0) { int da = (i >= 0 ? a[i] - '0' : 0) - borrow; int db = (j >= 0 ? b[j] - '0' : 0);
if (da < db) { da += 10; borrow = 1; } else { borrow = 0; }
temp[k++] = (da - db) + '0'; i--; j--; }
while (k > 1 && temp[k - 1] == '0') { k--; }
for (int t = 0; t < k; t++) { result[t] = temp[k - 1 - t]; } result[k] = '\0';}
void divide_bigint(const char *dividend, const char *divisor, char *quotient, char *remainder) { char rem[MAX] = "0"; char temp[MAX]; char q[MAX]; int qlen = 0;
for (int i = 0; dividend[i] != '\0'; i++) { int len_rem = strlen(rem);
if (strcmp(rem, "0") == 0) { rem[0] = dividend[i]; rem[1] = '\0'; } else { rem[len_rem] = dividend[i]; rem[len_rem + 1] = '\0'; }
normalize(rem, temp); strcpy(rem, temp);
int digit = 0; while (compare_num(rem, divisor) >= 0) { subtract_num(rem, divisor, temp); strcpy(rem, temp); digit++; }
q[qlen++] = digit + '0'; }
q[qlen] = '\0'; normalize(q, quotient); strcpy(remainder, rem);}
int main() { char n[MAX], m[MAX]; char quotient[MAX], remainder[MAX];
scanf("%s %s", n, m);
divide_bigint(n, m, quotient, remainder);
printf("%s\n", quotient); printf("%s\n", remainder);
return 0;}