글 읽기 - 너무 거저먹을려고 했나.... 시간초과 질문입니다

jhs061116 2년 전 0

20%에서 컷 당합니다..

#include<stdio.h>

int a1=0,b1=0;
int f(int n) {
    if (n == 0) {
        a1++;
        return 0;
    } else if (n == 1) {
        b1++;
        return 1;
    } else {
        return f(n-1) + f(n-2);
    }
}

int a,n;
int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%d",&a);
		f(a);
		printf("%d %d\n",a1,b1);
		a1=0; b1=0;
	}
	
	return 0;
}

swoon 2년 전 0

3, 4, 5를 손으로 직접 해보시면 어떠한 규칙이 있음을 알 수 있습니당

flappybird 2년 전 4

예시를 들자면 f(10)이 한번 실행될때 f(3)은 아주 많이 실행됩니다.

f(3)은 어떤 상황에서도 리턴값이 같으니, f(3)을 시간을 들여서 한번 구했다면, 그 값을 저장해두면 시간을 많이 줄일 수 있습니다.

메모이제이션 기법을 찾아보세요

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

문제

문제

출처

ICPC

너무 거저먹을려고 했나.... 시간초과 질문입니다

jhs061116 2년 전 0

swoon 2년 전 0

flappybird 2년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말