[백준/1312] 소수 | 런타임에러? | 부동소수점과 컴퓨터 연산에 대한 이해

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

1312번: 소수

투 포인터 헷갈려서 쉬운 문제 찾다가 된통 당한! 문제.. 단순하게 str로 바꿔서 풀면 런타임 에러가 난다. 백준 문제에서 오타 등의 문제가 아닌 알고리즘으로인해 런타임 에러가 난 경우는 처음이다. 그만큼 배울 점이 많아서 기록해본다. 이 문제는 컴퓨터의 부동소수점 연산에 대한 이해가 기반되어야 한다. 사실 문제에서 대놓고 힌트를 제공하고 있다.

첫 번째 줄에 A와 B(1 ≤ A, B ≤ 100,000), N(1 ≤ N ≤ 1,000,000)이 공백을 경계로 주어진다.

라는 입력 조건이 주어졌기 때문에, 두 수의 나머지 연산을 통한 값을 나누기가 표현할 수 없는 경우에도 출력을 해야한다.

[알고리즘]

컴퓨터는 실수(float, double)를 부동소수점 방식으로 저장한다. 컴퓨터는 모든 수를 0과 1로 저장하기 때문에 실수를 완벽하게 저장하지 못하고, 근삿값만 저장하게 된다. 파이썬에서의 실수형 유효숫자는 15개 정도이다. 따라서 str(a/b)는 정확하지 않고, 나눗셈 연산의 일부만을 보여주게 된다.

 

https://www.youtube.com/watch?v=-GsrYvZoAdA 

예전에 이 영상을 재밌게 봤던 기억이 있는데 막상 문제에서 만나니까 신기하고 더 기억이 잘 남고 재밌다..!!

 

따라서 이 문제를 해결하기 위해서는 단순 str 자릿수가 아닌 수학적인 방식을 고려해야한다.

1. a와 b를 나누어 몫을 구한다.

2. 1번에서 나온 몫과 b를 곱하여 a에서 빼준다.

3. 빼준 후 10을 곱하여 a에 대입한다.

- 여기까지 나눗셈 과정을 직접 써보면 이해하기쉽다.-

4. 바뀐 a에서 다시 b를 나눈다.

이 과정을 n번 반복하면, n번째 자리의 숫자를 구할 수 있다.

---

[전체코드]

a,b,n = map(int, input().split())

for _ in range(n):
     a = (a%b)*10
     ans = a//b
print(ans)