[python] 백준 1312번 소수

문제 풀이

해당 문제를 수학으로 접근하지 않고 나눈 다음 문자열로 생각하여 풀다 보니 IndexError와 틀렸습니다만 주구장창 떴다. 반례를 고려했다. 

 

아래는 처음 짰던 코드다.

25, 7, 5 가 입력되었을 때 25/7의 결과가 str() 함수에 의해 문자열로 바뀌고 해당 문자열을 ' . ' 으로 구분하면 몫과 소수 부분으로 나뉘게 된다. 25/7을 했을 때 3.5714285... 을 split(' . ')을 해주면 3과 5714285... 두 문자열로 나뉜다. 뒤에 인덱스를 붙여주면 list 형태가 되어 인덱싱을 했을 때 해당 5714285... 이 부분만 가져올 수 있다고 생각하여 풀었다.

a, b, n = map(int, input().split())
# 25/7 = 3.5714285... -> 3, 5714285...
str_list = str(a/b).split('.')[1]
print(str_list[n-1])

자꾸 indexError가 떠서 n이 0일때의 고려도 했었는데 문제에는 n의 범위가 N(1≤N≤1,000,000) 나와 있었는데 말이다. 조금만 더 생각을 더 해봤더니 1 / 6을 했을 때의 결과값이 아래와 같았다.

1을 6으로 나누었을 때의 결과

컴퓨터에서 실수를 표현하는 방법은 2진수로 표현하는데 부동소수점 방식을 따르고 있다. 그래서 정확도 문제에 오차가 있다.

부동소수점 - 위키백과, 우리 모두의 백과사전

1 / 6 을 했을 때의 결과값은 0.16에서 6이 순환소수 지점이 되어 N에 1,000,000이 들어왔을 때 6이 출력되어야 하는데 

해당 위의 결과값으로는 N으로 1,000,000이 들어왔을 때에는 IndexError를 발생시킨다.

 

그래서 접근한 방법은 수학으로 접근하는 것이었다. 아래의 그림을 보면 기본적으로 두 수의 나눗셈을 표현한 것이다. 보면 반복되는 부분이 있다. 아래의 과정을 보자.

1. A(25)와 B(7)을 나누어 몫을 구한다.

2. 1번에서 나온 몫과 B(7)을 곱하여 A(25)에서 빼준다.

3. 빼준후 10을 곱하여 A에 대입시킨다.

4. 바뀐 A의 값에서 B(7)을 나눈 몫을 배열에 삽입한다.

5. 1~4번의 과정을 반복한다.

 

위의 5번을 n번만큼 반복하면 해당 소수 n번째 자리의 수를 구할 수 있다.

차근차근 그림 대로 그려가며 이게 왜 이렇게 되는지를 직접 써보며 구현하다 보면 이해가 가능한 부분이다.

 

완성된 코드!!👍😊

a, b, n = map(int, input().split())
print(a/b)
sosu = list()
for _ in range(n):
    # (25 - (25 // 7)*7)*10 -> 두수를 나눠서 소수를 구하기 위한 방식
    a = (a - (a // b)*b)*10
    print(a)
    sosu.append(a // b)
print(sosu[n-1])