출처
Koreatech OnlineJudge(링크)
문제이해
입력으로 두 수 A, B가 주어지고 A/B를 순환마디를 표시하여 출력하는 문제이다.
예를 들어 0.123579579579... 를 출력한다고 하면 0.123(579)와 같이 출력하는 것이다.
만약 입력이 1, 4로 계산결과가 0.25가 되어 나누어 떨어진다면 0.25(0)처럼 표현한다.
문제접근
출력해야 할 수가 그림과 같이 0.123579579579... 라면
순환마디 시작점인 a와 끝점인 b를 구해야 한다.
그렇다면 순환마디가 어디까지인지는 어떻게 구해야 할까?
나눗셈을 할 때 매 과정마다 몫과 나머지가 나오고 나머지를 다시 나누는 과정을 반복하는데, 매 과정마다 이 나머지 값을 저장해 두고, 저장됐던 나머지와 같은 값이 나올 때 반복을 종료한다. 이 때 해당 나머지 값이 처음 나온 부분이 순환마디의 시작이며, 다시 나온 부분이 순환마디의 끝이다.
구현
매 과정마다 나머지 값이 이미 저장되어 있는지 검사해야 하므로 STL map을 사용하면 적절하다. STL map은 레드-블랙 트리를 사용하고, map::find()는 O(logn)으로 어떤 원소가 존재하고 있는지 검사할 수 있다.
반복문의 종료조건은 아래와 같이 두 가지이다.
- 나머지가 0이 되었을 때 (유한소수)
- map::find()값이 map::end()와 다를 때 (나머지값이 중복하여 등장했을 때)
printf()함수를 사용하여 출력할 때
printf("%.*s", length, str);
의 형태로 사용하면 str이라는 char배열을 length길이만큼 출력할 수 있다.
실행결과
코드
코드에서 for(;~scanf.... 와 같이 되어 있는 부분은 문제를 빨리 풀기 위해 작성한 것으로, 데이터를 입력할 때 EOF를 입력해 주어야 프로그램이 제대로 완료된다.
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1008/1008.cpp