큰 값을 나눗셈하는 소스코드 작성 시 주의할 점

백준 2869번 달팽이는 올라가고 싶다 라는 문제이다.

이 문제에서는 억단위의 숫자끼리 나눗셈을 수행하는 경우까지 처리해줘야한다.

시간복잡도 O(1)로 풀면 되는 문제인데도 정답율이 26%밖에 안되는 이유는 많은 이들이 어떤 사실을 모르고 있었기 때문이라고 생각한다. 이 어떤 사실이 무엇인지 설명하겠다.

www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

결론부터 말하자면 큰값에서 큰값을 나눈 값을 float형 변수에다가 저장하지 말자.

 

그 큰값이라고 한다면 대략 1600만을 넘어가는 값을 의미한다. (직접 실험해봄)

어떤 문제가 생기냐면, 소스코드상에서 나눗셈을 한다면 아주 미세한 오차가 발생한다는 것이다.

즉 나눗셈을 하는 값들의 크기가 커질수록 그 오차는 티끌모아 태산이 되어서 정수급 규모의 오차가 발생하게 된다.

 

큰값에서 큰값을 나누었을 때 나누어 떨어지는 여부를 판단하고 싶다면 가장 안전한 방법은 %를 이용하는 것이다.

애초에 %의 용도가 나머지를 구하는 용도가 아닌가?

즉 큰값에서 큰값을 나누고 싶을 때 몫은 int형으로 저장하고, 그 나머지를 구하고 싶을 때에는 %를 이용하면 된다.

 

용도에 맞게 만들어 준 대로 근본적인 방법을 이용하자

소스코드상에서 나눗셈을 하면 미세한 오차가 발생한다는 사실을 기억하자

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long a, b, v;
	cin >> a >> b >> v;
	if (a == v) {
		cout << "1";
		return 0;
	}
	if ((v - b) % (a - b) == 0) {
		cout << (v - b) / (a - b);
		return 0;
	}
	else {
		cout << (v - b) / (a - b) + 1;
	}
}