백준 13312 - 아크코사인은 믿음입니다 (C++)

문제 정보

• https://www.acmicpc.net/problem/13312
• 해 구성하기

---

문제 정리

자구이는 정수 N개를 전부 더한 뒤 100으로 나눈 값의 아크코사인 값을 계산하는 문제를 받았다. 그러나 자구이는 각각의 정수를 100으로 먼저 나눈 뒤 다 더하는 방식으로 잘못 계산했다. 원래 나와야 하는 값과 자구이가 출력하는 값의 오차가 0.001 이하가 되지 않도록 하는 반례를 찾아야 한다.

---

풀이

딱 봐도 부동소수점 오차를 이용하는 문제이다.
어디에서 부동소수점이 쉽게 발생하는지를 알아야 하기 때문에 아크코사인 함수 개형부터 살펴보자.

그래프는 대충 이렇게 생겼다. (코사인의 역함수니까 당연하긴 한데)

풀이를 쭉 적어보면 다음과 같다.

1. $a_1 + a_2 + ... + a_N = 100$을 만족하도록 값 $a_1, a_2, ..., a_N$을 적당히 정한다.
2. 그러면 $(a_1 + a_2 + ... + a_N) / 100 = 100 / 100$이 되고, 문제에 의해 $acos((a_1 + a_2 + ... + a_N) / 100) = acos(1) = 0$이 된다.
3. 그런데 자구이의 코드는 $a_1/100 + a_2/100 + ... + a_N/100$처럼 계산하므로 부동소수점 오차에 의해 총합이 정확하게 100이 되지 못한다.
4. 따라서 $acos()$의 값도 $0$이 되지 못하고 오차가 발생하게 된다.
5. 이 오차가 0.001보다 커지면 문제 해결!

합이 100이 되도록 한 이유는 다음과 같다. 기울기가 가파르면 $x$값이 살짝만 차이나도 $y$값, 즉 $acos()$값의 차이가 커진다. 그리고 $x=-1$일 때와 $x=1$일 때의 기울기가 가장 가파르기 때문에 합이 -100 또는 100일 때가 제일 좋기 때문이다.

라고 생각을 했다......

math.h의 acos() 함수가 뱉는 값을 봐보자.
https://en.cppreference.com/w/c/numeric/math/acos.html
C의 acos() 문서인데,

Domain error occurs if arg is outside the range [-1.0; 1.0].
If the implementation supports IEEE floating-point arithmetic (IEC 60559):
If the argument is +1, the value +0 is returned;
If |arg| > 1, a domain error occurs and NaN is returned;
if the argument is NaN, NaN is returned.

라고 적혀 있다. 즉, $acos(x)$에서 $|x| > 1$인 값이 들어올 경우 NaN값이 리턴된다는 것이다. 정리해 보면, 문제에서 찾고자 하는 것은 acos() 값의 차이가 0.001 이상 차이나는 값을 찾는 것이 아니라,
$a_1/100 + a_2/100 + ... a_N/100 = 1.000000000002$
처럼 값이 1 이상으로 튀어 NaN과 0 값을 비교해 오차 계산에서 에러가 나고, 오차가 0.001 이하가 되지 않도록 만드는 것이다. 왜 문제에서 "오차가 0.001 이상 되도록 해야 한다" 라고 적지 않았는지 이제야 이해를 했다...

아무튼 그렇다. 아래 코드는 $a_1 + a_2 + a_3 = 100$이면서 NaN 값을 뱉는 쌍을 찾는 코드이다. 문제에서 주어진 코드에 살짝만 수정한거라 거의 비슷하다.

---

코드

#include <stdio.h>
#include <math.h>
#include <cassert>
#include <stdlib.h>
const int LIM = 1000000000;

typedef long long ll;

float _abs(float x) { return x < 0 ? -x : x; }
bool is_equal(double a, double b) { return _abs(a - b) < 1e-3; }

int main()
{
	for (int i = 1; i <= 100; i++) {
		for (int j = 1; j <= 100; j++) {
			int k = 100 - i - j;
			if (-100 > k || k > 100)
				continue;
			ll tot = i + j + k;
			double wrongTot = i / 100.0 + j / 100.0 + k / 100.0;

			if (!is_equal(acos(wrongTot), acos(tot / 100.0)))
				printf("%d %d %d\n", i, j, k);
		}
	}
	return 0;
}