나머지 연산은 여러번 해도 값이 달라지지 않습니다.
100 을 99로 나눈 나머지는 1이고, 1을 99로 나눈 나머지는 1인 거죠..
arr 에 이전 계산 값을 넣은 것 같은데, 계산한 값이 0이 될 수도 있습니다. 그래서 -1과 같이 나오지 않을 수로 채우는 것이 더 좋을 것 같고..
15746 으로 나눈 나머지는 15746 보다 작으므로 long long 까지 쓸 필요는 없을 것 같습니다.
속도는 재귀없이 dp 로 푸면 더 빨라질 것 같습니다.
memset 도 하지 말거나 (global 변수는 항상 0으로 초기화)
n 을 입력 받은 후 n개만 초기화하는 것도 속도를 빠르게 할 수 있을 것 같습니다.
akqjqcjs7 3년 전
f함수 내에서 arr[n]!=0이면 그대로 arr[n]을 반환합니다. 이렇게 제출하니 코드도 정답이 나왔습니다. 그런데 여기공식을 arr[n] % 15746을해도 정답이
나옵니다. 제 생각으로는 n = 100일때 arr[100] = (f(99)+f(98))%15746이라한다면 f(99)는 재귀를통해 리턴받고 f(98)은 arr[98]을 바로 리턴받습니다.
하지만 arr[98]도 이미 재귀를 통해 15746을 나눈 나머지를 저장한 값일텐데 여기다가 다시 15746을 나누어도 문제가 없는지 이해가 가지않습니다.
그리고 여기서 시간을 더 단축할 수 있는 방법이 있을까요?