citizen   3년 전

https://www.acmicpc.net/blog/view/28 에 있는 내용을 가지고

메모이제이션을 하는 방법으로 피보나치 수를 구하는 함수를 긁어왔습니다.

다른 피보나치 문제들은 모두 아래와 비슷하게 코딩해서

통과를 받았습니다만, 이 문제만 통과를 못하고 있네요.


(안 푸신 분들을 위한 본문 요약)

"T개 만큼의 테스트 케이스가 주어지며

각 테스트 케이스마다 한줄에 P와 Q가 주어지고

P번째 피보나치 수를 Q로 나눈 나머지를 구하라"

정도 입니다.

Q를 전역변수로 두었고 피보나치수의 값들은 해시에다 저장을 해 두었으며

각 테스트케이스가 끝나기전에 해시를 비워두었습니다.(안 비워두면 다음 테스트케이스의 Q값이 적용이 안되므로)


생각지 못한 반례라도 있을까요?


dlwodnsdl   3년 전

직접 사이트 가서 문제보니까 P랑 Q랑 범위가 반대로 되어있네요. 

citizen   3년 전

길이가 10000인 배열로 풀었을 때 런타임에러가 안 생기는걸 보니

P가 10000보다 작은거였군요.. 흠

citizen   3년 전

그런데 아직도 궁금한게,

P와 Q의 값의 범위가 위 풀이의 답에 어떻게 지장을 주는지에 관한것인데..(int형을 벗어난것도 아니고..)

그 이유에 대해서는 아직 확신이 서지 않네요.


dlwodnsdl   3년 전

44번째 줄에 

long val = ((2*t1 + t2)*t2)%Q

여기서 오버플로우가 발생할 수 있을 것 같습니다.

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