c에는 매우 큰 정수에 대한 데이터 타입이 없어서 문자 배열로 입력받고 나눗셈을 구현했지만, 제출 시 중간에 시간초과가 발생합니다.

quot = dvd / dvs, rem = dvd % dvs를 구하는 과정이며, 구현에 사용된 알고리즘은 다음과 같습니다.

1. L23 ~ L26: 먼저 수를 입력받아 나누어진느 수를 dvd 문자열에 나누는 수를 dvs 문자열에 저장한 후, 계산의 편의를 위해 my_strrev()함수를 통해 배열 순서를 뒤집었습니다. 예를 들어,

123 45

 와 같은 입력이 주어질 경우, dvd = {'3', '2', '1', '\0', ...}, dvs = {'5', '4', '\0', ...} 이 됩니다. 편의를 위해 이후에는 dvd = 123, dvs = 45과 같은 방식으로 표기하겠습니다.

2. L28 ~ L41 (예외 처리): dvd와 dvs의 자릿수(배열의 길이)를 비교한 후 같으면, cmp() 함수를 통해 dvd와 dvs의 크기를 비교하고 dvd가 dvs보다 작을 경우, my_strrev()함수를 통해 다시 배열 순서를 뒤집어, 0과 dvd를 출력합니다.

3. L43 ~ L46: 계산 속도를 줄이기 위해 미리 dvs의 i(1 <= i <= 9) 배수값을 dvd_mul[i]에 저장합니다. mul_to()함수 속에 자리 올림까지 구현했습니다.

4. L48 ~ L65: dvd의 가장 큰 자릿수값을 dvs의 가장 큰 자릿수 값 + 1로 나누어 얻은 몫이 m이면, dvd - dvs * m * 10^k를 dvd에 저장합니다. 여기서 k는 dvd와 dvs의 자릿수 차이입니다. 예를들어, 입력이

9888 30

인 경우, 9888 - 30 * 2 * 10^2 = 3888이 새로운 dvd값이 됩니다. 입력이

3888 30

인 경우, 3888 - 30 * 9 * 10^1 = 288이 새로운 dvd값이 됩니다.

위 과정을 dvd의 자릿수가 dvs의 자릿수와 같아질 때까지 반복합니다.  위 과정 동안 quot[k] 에 m을 더해줍니다.

5. L67 ~ L79: dvd와 dvs의 자릿수가 같을 경우, dvd와 dvs의 크기를 비교한 후 dvd가 dvs보다 크거나 같으면, dvd에 dvs에 특정 수 m을 곱한 값을 빼줍니다. 이때 quot[0] 에 m을 더해줍니다.

6. dvd가 dvs보다 작아진다면 dvd의 값은 나머지가 됩니다.

7. 4번 5번 과정에서 구한 quot 배열을 자리올림 후 ascii코드로 변환하면 quot가 몫이 됩니다.

테스트 예시

input:

94123905780121437589413769034769034673489056745906745896754570349827502348956234906723490578234917239572915873490670934276493025792305790437593402875349028675094316134908673490567349567239067239672896702348956238905630485613089563498573495792345679342672907560234967390572905679234567239561290569023563905639025639025609235690235623956720395672390565349185701934670134895673489674526089342758934651738456437895672347859623498576423856348907345298602745890346153489560713859004365819350614239805613405793246578031465093148561207895621978561204623956234785623489562934856384795612789563478561348956134985678934265893426589326582396589324652389658923653478965348965783613785613965349759836590346598567239047234895634956734190601910573489578349513656134856138561390457340895619084672398574890561349056340789571389674098561390856134905613904567340562352368957134689576134957634890563408563407956347056907456128905693408571390857139864590237456239657834561385618295619856923569325693256925695615619195638952 3003124325643642367353495703492750984327590234705923470592347095512353634735892345890347560914736983467803476439057902357042395702395797492374

output:

31341994394437333898854863910308897468680294999188328696952226599196965771958363814065838779905607123967157783819417180002545496154809588440459169143665611758149813862007645352042234773512139556686438970095332774080442171760201437652273140432332575394343919251325461140096357601090164832951332961014958469880029697111230944442935396392176800820953539603725991294241958915044267601902477022347125202447148775081681840499660655254100977829296371904505878525534208225079373642425267628681780689720457417085421471887064003765253896834122287009143112246608346169918153111033371139048097625631649157712004074590903848223697237773310490861609711484314059039273231625375189950901882119091398387446973634464116566267670558227729438754033592379746323325570605695327632204847248013174489269023065877922121034789904865521654731473118565669297600076890425857371212922614247
2260216010134418806707674633961594541943165491136099276146930589728234008593382545875899271061328926195400857168234250880190503678940069386574

output의 정답 유무는 python으로 확인했습니다. 위와 같은 1000자리 수 나눗셈에서도 0.1초 내에 동작하는 것을 보아 알고리즘 자체의 시간 복잡도 문제는 아닌 것 같습니다.

4번이나 5번 과정중 무한루프가 발생해서 늦어지는 것으로 추측해봤지만, m이 1 이상인 경우, for문은 반드시 끝나야합니다. 중간에 m이 0이 될 수 있는 반례는 못찾겠습니다.