simm4256   3년 전

https://www.acmicpc.net/source...

정답 처리된 위 소스로 아래 테스트 케이스를 돌려보면

1번 테스트 케이스에서 0이 나오고, 2번 테스트 케이스에서는 1이 나옵니다.

https://www.acmicpc.net/source...

이 소스에서는 1번 TC가 1이 나오지만 2번 TC에선 0이 나오네요.

둘 다 1이 나와야 합니다.

kks227   3년 전

https://www.acmicpc.net/board/... 글 잘 읽었습니다.

네이버 블로그 댓글을 타고 와서 본 글이긴 한데 지금 정말 공교롭게도 네이버 블로그가 정기 점검 중이라 답댓글을 달 수도 없고 추가로 제 이번 학기 공부 방식인 복습글 포스팅도 불가능하여 공부도 못 하고 있는 처지입니다. 그래서 그냥 여기에 제 짧은 소견 밝히도록 하겠습니다.


일단 이 테스트 케이스의 목적은 입실론을 허용하지 않고, 어떤 좌표가 소수인 지점에서 정확히 T인 시간에 만날 수 있는 경우를 제대로 판별하게 하기 위함이라고 이해했습니다.

그런데 사실, 프로그래밍 대회에 있어서 실수 오차 범위는 허용해주는 것이 맞다고 (저는) 생각합니다. 일단 컴퓨터가 절대 모든 실수를 정확히 표현할 수 없다는 것도 이미 유명한 사실이고, 그래서 잘 만들어진 실수와 연관성이 높은 문제들은 문제, 입력, 출력 조건에서 오차범위에 대한 어떤 조건을 제시합니다. 정답과의 차가 1e-6 이내면 정답이라거나, 문제에서 ~~~한 값이 1e-6 이내인 경우는 없다던가...

저도 이 문제를 풀면서 의아함을 느꼈던 것이, 두 번째 예제 케이스에서 x=10, x=5에 있던 학생은 정확히 T=2.5일 때 x=7.5 지점에만 만날 수 있습니다. 이것이 바로 끝점에서만 만나는 예시인데, 이 예제의 등장으로 인해 마지막 순간에 정확히 끝점에서만 만나는 경우도 제대로 처리해야 한다는 건 확실해졌고, 별다른 문제없이 이걸 대부분의 사람들이 처리한 이유는 하필 2.5나 7.5 모두 0.5의 배수이기 때문입니다. 0.5는 2^k 꼴의 수 중 하나이고, 일정 범위 안에서 실수 자료형이 정확히 표현할 수 있어서 문제가 생기지 않은 것으로 알고 있습니다. 어쨌거나 예제를 보면서 좀 '이래도 되나...?' 싶은 생각을 했고 좀 불안해하며 제출을 했는데 맞긴 맞았습니다만... 이후 따로 처리는 안 했습니다. 귀찮아서...


파싱을 하거나 하여 10000배를 하면 정확한 비교가 가능하다고 제시하셨지만, 이것으로도 끝은 아닙니다. 해당 글 마지막에 있는 소스 코드에

2 1000000000
0 1000000000
999813528 1000000000

이 케이스를 넣어 봅시다. 아니 상식적으로 저건 무조건 가능할 수밖에 없습니다. 그러나 출력은 1이 아니라 0이 나옵니다. 이는 v*T*10000이 너무 커져서 64비트 정수형으로 절대 표현할 수 없어서 생긴 일입니다. 어떻게 예외처리를 해서 거를 수는 있습니다. 예를 들면, 실제로 저런 학생이 존재한다면 그냥 그 학생은 0~1000000000의 모든 범위의 학생이 있는 위치를 다 커버합니다. 답이 그냥 1이 될 것입니다. 아니면 자리올림을 하듯이 64비트보다 약간 큰 정수형을 보존하는 클래스나, 그냥 빅인티저를 만들어 쓸 수도 있겠군요.


그러나 문제가 또 있습니다. 저렇게 범위를 넘어가는 값을 넣지 않더라도,

2 32.1112
0 289
1 8

이걸 넣어봅시다. 32.1112*(1+8) = 289.0008이니까 저 둘은 만나겠지요. 하지만 역시 결과는 0이 나옵니다. 이는 myT = (long long)(t * 1e4); 때문입니다. myT가 실제로 321112가 아닌 321111로 저장되어서 나와버리는 문제고 이 또한 실수 오차 문제지요. 따라서 글 중간에 나온 것처럼 진짜 문자 단위로 파싱을 하면 이 문제는 막을 수 있습니다.


뭐 이렇게 해서 문제는 많지만 다 예외처리로 땜빵을 가하면 맞을 수는 있습니다. 하지만 이 케이스들이 말해주는 것은 신경쓸 게 한 두 가지가 아님이 확실하다는 점이라고 생각합니다. 문제가 점점 하드코딩이 요구되게 변질되고 있죠.

그래서... 저는 그냥 이 문제의 테스트 케이스를 추가한다기보다는, 차라리 기존의 테스트 케이스를 다듬어서 실수오차에 민감하지 않도록 바꾸는 것이 더 좋다고 생각합니다. 여기서부터는 개개인의 의견이 다를 수 있는데, 초심자 전용 문제들로 만든 셋이 본래 취지이니까(뭐? L번이?), 이미 대회는 끝났지만 문제가 초심자 전용이 전혀 아니게 바뀌어버리는 일은 살짝... 부자연스럽다고 저는 생각합니다.

부족한 글이었습니다. 감사합니다.

kks227   3년 전

사실은 다 필요없고 그냥 재채점해서 틀리기가 두려운 한 사람의 사사로운 감정이 일궈낸 글입니다.

chogahui05   3년 전

초심자용 문제라기에는 B번이 (생각보다 많이) 어렵더라고요.. K나 L번이면 이해는 하겠지만요.

처음에는 이게 보다보니 acm icpc 인터넷 예선 문제에 나왔던 교차점 문젠가? 라고도 생각했는데요.

(그것과는 다르게) 소숫점 때문에 머리 아팠던 기억이 납니다.


요 문제 풀면서 복잡한 케이스 따지는 방법을 배우긴 했습니다. 실수 오차랑.

저는 실수 오차가 무서워서 0.5단위로 끊어지는 수리공 항승이라는 문제 조차도. 2배를 한다던지..

이게 습관처럼 되어버리더라고요. 0.5단위면 딱 떨어지는 것인데도요.

kks227   3년 전

사실 기존에도 잭 바우어라던가 하는, 출제자가 의도한 것인지는 알 수 없지만 실수오차에 굉장히 민감하게 반응하는 문제가 몇 개 남아 있긴 합니다.

들쥐의 탈출 문제도 실수오차 때문에 뼈대 알고리즘을 알아내도 틀리는 경우가 많았습니다. 지금은 어떤지 모르겠습니다. 재채점을 한 번 한 적 있어서...

어쨌거나, 이 대회 취지가 "초심자 전용 문제들"이었으리라고 추측한 바를 토대로 이 문제에 실수오차에 민감하게 반응하는 TC를 추가하는 방향보다는, 차라리 문제에 "어떤 두 사람의 위치의 차가 0.000001 이하면 만난 것으로 친다." 등의 실수오차에 관대한 조건을 넣는 방향이 더 바람직하지 않은가...라고 저는 생각합니다.

물론 제 생각이니까 어디까지나 개인의 의견입니다. 백준님의 판단이 결정할 일인 것 같습니다. (그리고 지금까지 제출된, 제 것을 포함한 수많은 코드들의 운명도...)

kks227   3년 전

확인해보니까 들쥐의 탈출 문제는 재채점 이후 기존에 실수오차 때문에 틀렸던 코드들이 맞아 있네요.

startlink   3년 전

데이터를 추가했습니다.

https://www.acmicpc.net/rejudg...

댓글을 작성하려면 로그인해야 합니다.