1008: 순환 소수

Link : judge.koreatech.ac.kr/problem.php?id=1008

---

1. 문제

• 두 정수 A, B 가 주어졌을 때 A를 B로 나눈 결과(A/B)를 순환 소수 형태로 출력하세요. (B != 0)
  순환되는 부분은 괄호 안에 출력하도록 합니다.
  만약 숫자가 나누어떨어질 경우 괄호 안에 0을 출력하세요.

 

---

2. 문제의 조건

• 1 <= T <= 1,000
• 0 <= A <= 100,000
• 1 <= B <= 100,000

 

---

3. 문제 접근

• 시간 복잡도
  
  제한시간이 1초이므로 testcase는 약 1000개, O(N^2.666) 시간 내에 풀면 된다고 생각했습니다.

 

• 아이디어
  
  대표적으로 순환소수에는 3가지의 형태(?)로 나뉘어집니다.
  1/8 = 0.125
  1/13 = 0.076923076923
  1/14 = 0.0714285714285
  
  감히 잡히시나요?? 순환소수가 아닌 것과 순 순환 소수, 혼 순환 소수로 나뉘어집니다.
  2번 째 케이스의 경우 076923 이 반복되며 처음부터 반복을 시작합니다. 이런 경우는 순 순환 소수라고 불리웁니다.
  하지만, 3번 째 케이스를 보시면 714285로 소수점 2번 째 자리부터 반복을합니다. 이것은 혼 순환 소수라고 합니다.
  
  시간복잡도를 구하는 방식이 어려우니 추후 생각하기로 하였습니다.

 

---

4. 풀이 방법

• 앞자리의 몫을 구해줍니다.
• 이제 뒷자리를 구해줍니다.
  만약 나머지가 0이라면 더 이상 나눌 것이 없는 것이므로 순환소수가 아닙니다.
  
  

  

  
  만약 나머지가 0이 아니면서 나머지가 처음과 같다면 이것은 순 순환 소수입니다.
  

  

  
  
  만약 나머지가 0이 아니면서 나머지가 처음과 같지 않으면서 현재 계산한 나머지가 이전 기록에 있다면 그 이전 기록의 idx부터 현재까지가 반복되는 구간입니다.
  
  

  

 

---

5. 소스코드

• cjw-git.tistory.com/82

 

---

 

cjw.git@gmail.com