문제가 이거인데
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#include <iostream>
using namespace std;
int N[1002];
int func(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (N[n] != 0) {
return N[n];
}
N[n] = func(n - 1) + func(n - 2);
return N[n];
}
int main() {
int n;
cin >> n;
cout << func(n) % 10007;
return 0;
}
이게 틀렸다고 나온 소스고
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#include <iostream>
using namespace std;
int N[1002];
int func(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (N[n] != 0) {
return N[n];
}
N[n] = func(n - 1) + func(n - 2);
return N[n] % 10007;
}
int main() {
int n;
cin >> n;
cout << func(n);
return 0;
}
이게 정답 소스거든??
둘 차이는
% 10007 을 출력할 때 해주는가 vs 함수에서 리턴할 때 % 10007 을 해주는가
차이밖에 없는데 왜 첨에는 틀렸다고 나온거야?
난 왜그런지 몰겠어...
왜 나머지를 출력하라고 했을거같아?
숫자가 졸라게 커지니까?
앗 알겟다 ㄳ ㅎㅎ
이미 값이 오버플로우 난상태에서 %해봐야 소용없으니깐
그러네 이제 알겠다 ㄳㄳ
문제 안읽고 코드만 보면 func()가 int를 리턴하는데 리턴할 때 % 10007을 안하게 되면 예를 들어 INT_MAX보다 더 큰 값을 리턴하게 되면 리턴 값에 변화가 오겠지? 범위가 int니까 근데 리턴할 때 % 10007을 하게 되면 최대 리턴값에 10006이니까 int 범위를 넘을 일이 없겠지? 그 차이
그생각을 못했었어 ㅋㅋㅋ 고마워
피보나치 수열이기 때문에 for문 하나로도 풀수있음
하향접근식 쓰냐 상향접근식 쓰냐 그 차이겠지 뭐
bottom up/top down
O(logN)도 가능하네
https://mono-cake.coffee/2020-03-28-fibonacci/
한번 봐야겠다