백준 11571 분수를 소수로(구현)

https://www.acmicpc.net/problem/11571

11571번: 분수를 소수로

개인적으로 엄청 어려운 문제였다.

처음에 접근한 방법은 소수점 아래의 숫자들을 문자열이라고 치고 반복적으로 나타나는 패턴을 찾기 위해 

브루트포스를 이용하거나 한번 나온 숫자가 뒤에 다시 나올 떄 조건을 두는 방식으로 했는데 잘못된 생각이였고 잘 풀리지 않았다.

분수를 소수로 바꾸는 과정은 위의 사진처럼 나눗셈을 하면서 나머지에 대해 처리를 해주면서 진행이 된다.

나눗셈을 하면서 나머지가 계속 나올텐데 한번 나온 나머지는 그다음부터도 똑같은 패턴으로 나눗셈이 진행되기 때문에 나눗셈을 하면서 나오는 나머지를 기억해줄 필요가 있다. 

 

나머지를 기억해줌과 동시에 그때까지의 몫을 기억한다면 확실한 풀이가 가능할 것이다.

 

최종적으로 Dictionary에 나머지를 key, 몫에 대한 값을 value로 지정하면 되는데 

value는 나눗셈의 결과인 몫을 새로운 list에 추가해주면서 그 리스트에 len()으로 해주었다.

t = int(input())
for _ in range(t):
    a,b = list(map(int,input().split()))
    temp = str(a//b) + '.'
    a %= b
    hist = dict()
    while True:
        a *= 10
        if a not in hist.keys():
            print(temp)
            hist[a] = len(temp)
            temp += str(a//b)
            a %= b
        else:
            print(hist)
            print(temp[:hist[a]] + '(' + temp[hist[a]:len(temp)]+ ')')
            break