fhskf94kr   2년 전

repeated squaring algorithm를 참고하여 알고리즘을 구현하였습니다만, 여러가지 테스트 케이스를 입력해보고 제대로 된 결과가 나왔으나

본 문제에서는 틀렸다고 나옵니다.

질문 검색을 통하여 나오는 코드를 참고해보았지만 다른 부분을 찾을 수가 없었습니다.

*

알고리즘은 다음과 같이 구현했습니다.

범위가 int 타입을 벗어나지 않으므로 A,B,C는 int 타입으로 입력을 받았습니다.

이를 cal 함수로 넣고, 해당 함수에서는 범위 밖으로 벗어나는 것을 방지하기 위하여 double 값으로 연산을 수행하였습니다.

*

cal 내부에서는 B가 짝수이면 제곱수를 반으로 줄인 후 cal 연산을 수행하였고, 그 결과를 tmp 변수에 저장하여 tmp * tmp % C 결과를 return 했습니다.

B가 홀수이면 제곱수를 -1 한 후 반으로 줄인 후 cal 연산을 수행하였고, 그 결과를 tmp 변수에 저장하여 A *( tmp * tmp % C) % C 결과를 return 했습니다.

B의 값이 0일 때는 1을 리턴하여 B-1/2 의 값에서 오류가 발생하지 않도록 하였고, B의 값이 1일 때는 A%C를 return 하여 B가 1이 들어왔을 때 오류가 발생하지 않도록 구현했습니다.

본 코드에서 제가 수정해야 할 부분에 대해서 조언 및 힌트를 주시면 감사하겠습니다.

djm03178   2년 전

실수형은 정수형과 같은 바이트 수를 차지하고도 훨씬 더 넓은 범위의 수를 100% 정확하게 나타낼 수 있는 마법의 자료형이 아닙니다. 정확하게 표현할 수 있는 자릿수에 제한이 있기 때문에 더 넓은 범위를 표현하는 것이 가능한 거죠. tmp * tmp 같은 연산을 수행하면 상당한 오차가 발생할 수 있습니다.

오차가 안 나게 하려면 정수형만을 사용해야 합니다. 그런데 int는 너무 작죠. 그러면 뭘 사용해야 할까요?

fhskf94kr   2년 전

@djm03178 감사합니다. 정수형을 받아서 소숫점이 아닌 정수 값으로 단순 나머지 연산을 하면

오차가 발생하지 않을 것이라고 지레짐작하여 사용했었네요.

답변 감사합니다 ^^

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