글 읽기 - C++ 피보나치 수 2

ryan2020 3년 전 0

뭐가 이상한가요?

재귀로 푸는건 맞는것 같은데...

#include <cstdio>
#include <algorithm>
using namespace std;

int fibo(int x){
	if (x==0) return 0;
	if (x==1) return 1;
	return fibo(x-1)+fibo(x-2);
}
int main()
{
	int a;
	fibo(a);

	return 0;
}

mizuharaeki 3년 전 1

재귀로 풀면 시간초과 납니다.

DP를 이용해 푸는 문제입니다.

ryan2020 3년 전 0

감사합니다:)

mizuharaeki 3년 전 1

당연히 알고계시겠지만, 입력값도 안 받으셨네요. 그 부분도 체크하시면 될 것 같습니다.

ryan2020 3년 전 0

코드 바꿨는데도 이상하네요....

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

vector <int> dynamic;
int fibo(int x){
    if (x==0) return 0;
    if (x==1) return 1;
    if (dynamic[x]!=-1) return dynamic[x];
    
    dynamic[x]=fibo(x-1)+fibo(x-2);
    return dynamic[x];
}
int main()
{
    int a;
    scanf("%d",&a);
    dynamic.resize(a+1,-1);
    printf("%d",fibo(a));
    
    return 0;
}

mizuharaeki 3년 전 0

문제를 너무 어렵게 접근하신게 아닌가 생각이 드는데요.

이 코드를 드릴테니 해당 코드를 잘 활용해보시면 될거에요.

참고로 DP 는 재귀보다는 반복문으로 푸는 문제가 많습니다.

잘 읽어보시고 화이팅 하세요.

#include<iostream>
using namespace std;

long long int memo[91];

int main(void){
    int n;
    cin >> n;

    memo[0] = 0;
    memo[1] = 1;
    for(int i=2; i<=n; i++)
        memo[i] = memo[i-1]+memo[i-2];

    cout << memo[n] << endl;
}

3587jjh 3년 전 2

답의 크기가 int범위를 넘기 때문에 long long으로 바꿔야합니다. Dp 해결에 메모이제이션과 반복분을 이용하는 방법 양쪽 다 알아두는게 좋습니다

ryan2020 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

C++ 피보나치 수 2

ryan2020 3년 전 0

mizuharaeki 3년 전 1

ryan2020 3년 전 0

mizuharaeki 3년 전 1

ryan2020 3년 전 0

mizuharaeki 3년 전 0

3587jjh 3년 전 2

ryan2020 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말