부동소수점 오차로 추정되긴 하네요
(밑 코드는 AC 받은 코드입니다.)
24267번 - 알고리즘 수업 - 알고리즘의 수행 시간 6
파이썬에서 /는 부동소수점형 나눗셈 연산이라서 (int)/(int)이고 이론상 나누어떨어지더라도 결과는 int가 아닌 float로 반환되고, 값이 아주 크면 유효숫자의 손실이 일어날 수 있습니다.
정답 코드는 /6을 밖으로 꺼냈기 때문에 /6을 하기 전까지 정확한 정수값을 유지하며, /6을 한 결과는 float이긴 하지만 이론상 자연수이므로 오차가 거의 나지 않습니다.
그러나 나누기를 각 항에 분배하게 되면 3개의 float를 더하게 되는데 이것들은 이론상 정수가 아닐 수 있으므로 상당한 오차로 인해 값이 틀어질 수 있습니다.
분수(정수가 아닌 유리수)가 발생하는 순간 값은 무조건 틀린다고 생각하고, 모든 계산 과정 중에 항상 정수만 등장하도록 식을 설계하는 것이 좋습니다.
어느 언어든 실수 간의 연산은 부동소수점 오차가 발생할 수 있기 때문에 위험을 감수해야 하는 방법입니다. 이 경우 어떻게 실수 연산을 하느냐에 따라 실수 오차가 발생할 수 있으며, 이 작은 실수 오차가 정답을 판가름할 수도 있습니다.
이 문제의 경우에도 실수 연산 없이 정수 연산만으로 충분히 연산 횟수를 구할 수 있는 문제입니다. 가능한 한 수식을 실수 연산이 아닌 정수 간의 연산으로 바꿔주실 것을 추천드려요. Python의 경우 "/" 대신 "//" 를 사용할 수 있습니다.
아래는 두 번째 수식을 사용했을 때의 반례입니다.
입력: 499998 정답: 20832958335499996 3 출력: 20832958335499992 3
첫 번째로 답글을 달아주신 분의 코드를 보시면 아시겠지만, 실수 연산을 단 한 번도 하지 않고 오로지 정수 연산만으로 답을 구하고 계십니다.
댓글을 작성하려면 로그인해야 합니다.
kohhtbaekk113 2년 전
일단 문제 보자마자 당연히 sigmak=1n-2 k(k+1)/2 라는 식이 떠올랐는데 옆에 노트 두고 끄적이다가 울프람 알파 돌려서 식을 얻었음.
근데 제대로 코드를 썼는데도 오답 뜨길래 괄호도 쳐보고 혹시 예외처리 해야 되나 해서 값이 0이면 +1(어쨌든 나머지 코드라도 읽긴 읽은거니까)도 해보고 최고차항이 이상해서 그런가 싶어서 0, 1에서는 3 대신 4도 출력시켜보고 온갖 방법을 다 써봤는데 안 됨.
근데 식을 바꾸니까 바로 정답처리가 되네?
정답 뜬 코드는 이거고: print(int((n**3 - 3*(n**2) + 2*n)/6))
오답 뜬 코드는 이거임: print(int(n**3/6 - (n**2)/2 + n/3))
즉, 얘는 틀린 식이고,
얘는 맞는 식이라는 거.
참고로 두 식에 따른 각각의 코드 모두 컴파일러에서 출력은 문제없이 잘 됨. n=1, 2 둘 다 0으로 출력되고 100 이상 큰 수도 동일하게 나옴.
근데 하나는 맞다고 나오고 하나는 틀렸다고 나오니 뭐가 문제일지 감도 안 잡힘.