[Python 3] BOJ - 18117 "분수"

 #문제 링크 : https://www.acmicpc.net/problem/18117

18117번: 분수

 # 풀이 :

개인적으로 이 문제의 핵심은 실제로 단계별로 나눠주며 규칙성을 파악하는 것이라 생각한다. 우선 유리수의 특징을 생각해보자. 유리수는 소수로 나타내었을 때 항상 유한소수 혹은 순환소수 두가지 경우로 귀결된다.

<그림 1. 2 / 7 예시>

 위 그림 1을 보면 2/7의 경우가 있다. 현재 빨간색 글자는 소수점 아래의 첫번째 자리 수이고, 파란색 글자는 설명의 편의를 위해 소수점 아래의 첫번째 자리 수의 나머지로 정의하겠다. 

<그림 2. 2 / 7 예시>

 다음 단계의 그림을 나타낸 그림 2이다. 그림 1에서 정의한 바에 따라 소수점 아래 두번째 자리 수는 8이고, 소수점 아래 두번째 자리 수의 나머지는 4이다. 

<그림 3. 2 / 7 예시>

 다음 단계의 그림을 나타낸 그림 3이다. 정의에 따라 소수점 아래 세번째 자리 수는 5이고 소수점 아래 세번째 자리 수의 나머지도 5이다. 그런데 현재 소수점 아래 세번째 자리수의 나머지인 5에 10을 곱하고 7을 나누면 몫과 나머지는 각각 곧 소수점 아래 네번째 수, 소수점 아래 네번째 수의 나머지가 된다. 그런데, 5는 2 * 10 ^ 3 = 2000을 7로 나눈 나머지와 같다.

 따라서, a / b의 i번째 자리의 나머지는 a * 10 ^ i를 b로 나눈 나머지이다. 따라서, a / b의 i + 1번째 자리 수는 위 단락에서 본 바와 같이 a / b의 i번째 자리의 나머지에 10을 곱한 수를 다시 b로 나눈 몫이 된다. 따라서 a / b의 소수점 아래 i번째 나머지를 Mi, a / b의 소수점 아래 i번째 수는 Si라고 한다면 관계식은 아래와 같다

 

 # 코드

import sys

# ans : 정답 배열
ans = []

# tc : 테스트케이스 입력
tc = int(sys.stdin.readline())
for q in range(tc):
    temp = ''
    a,b = map(int, sys.stdin.readline().split())
    
    # 어차피 맨 처음 나오는 몫은 무의미하므로 제거
    a -= ((a // b) * b)
    
    i, n = map(int, sys.stdin.readline().split())
    
    # 관계식에 따라 i부터 i + n - 1까지 수를 구하면서 빈 문자열에 더한다
    for k in range(i, i + n):
        temp += str(((a % b * pow(10, k - 1, b)) % b) * 10 // b)
    ans.append(temp)
    
# 정답 출력
for t in ans:
    print(t)