[Jungol] 정올 3115 긴 자릿수 나눗셈

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2397&sca=5090

Approach

- 나눗셈 연산은 다른 ±, × 연산처럼 각 자리에서 바로 값을 정하기 쉽지 않습니다.

- 나눗셈 연산은 뺄셈 연산을 이용해서 구합니다.

   즉, 각 자리에서 뺄셈이 가능하면 몫을 1 증가 시키고 해당 수치로 빼다가 불가능해지만 다음 자리로 이동합니다.

---

#include <stdio.h>
const int LM = 210;
int strlen(const char* s, int len = 0){
       while (s[len]) len++;
       return len;
}
 
int strcmp(const char* s, const char* t){
       while (*s && *s == *t) s++, t++;
       return *s - *t;
}
 
void encode(char* s, int len, int num[]) {
       for (int i = 0; i < len; ++i) {
              num[i] = s[i] - '0';
       }
}
 
int minus(int* a, int* b, int len) {
       for (int i = 0; i < len; ++i) {
              if (a[i] > b[i]) break;
              if (a[i] < b[i]) return 0;
       }
       for (int i = len - 1; i >= 0; --i) {
              a[i] -= b[i];
              if (a[i] < 0) {
                     a[i] += 10;
                     a[i - 1]--;
              }
       }
       return 1;
}
 
void devide(char* ap, int an, char* bp, int bn) {
       int A[LM] = { 0 }, B[LM] = { 0 };
       int div[LM] = { 0 }, i;
       encode(ap, an, A);
       encode(bp, bn, B);
       for (i = 0; i <= an - bn; ++i) {
              while (minus(A + i, B, bn)) div[i]++;
              A[i + 1] += A[i] * 10;
       }
       if (div[0]) printf("%d", div[0]);
       for (i = 1; i <= an - bn; i++) printf("%d", div[i]);
       printf("\n");
}
 
int main() {
       // freopen("input.txt", "r", stdin);
       while (true) {
              char astr[LM], bstr[LM];
              scanf("%s %s", astr, bstr);
              if (astr[0] == '0' || bstr[0] == '0') break;
              int alen = strlen(astr), blen = strlen(bstr);
              if (alen > blen || (alen == blen && strcmp(astr, bstr) > 0))
                     devide(astr, alen, bstr, blen);
              else devide(bstr, blen, astr, alen);
       }
}