이도현

1. 피보나치 수 2

1. 접근 방법

시간 초과로 인한 메모이제이션

public class BOJ2748 {
    static long[] memo; //전역 배열 선언
    static long fibonnaci(int x) {
        if (x <= 1 ) {
            memo[x] = x;
            return x;
        } else if (memo[x] != 0) {
            return memo[x]; //이미 할당된 값
        } else { //0 - 할당되지 않음
            return memo[x] = fibonnaci(x - 1) + fibonnaci(x - 2);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new long[n + 1]; //배열크기 정하기 (초깃값 0)

        System.out.println(fibonnaci(n));
    }
}
Java
복사

재귀 ⇒ 점화식 : f(n) = f(n-1) + f(n-2)

public class BOJ2747 {
    static long fibonnaci(long x) {
        if (x == 0) {
            return 0;
        } else if (x == 1) {
            return 1;
        }
        return fibonnaci(x-1) + fibonnaci(x-2);
    }
    //피보나치 수 1
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        System.out.println(fibonnaci(n));
    }
}
Java
복사

2. 파도반 수열

for문 + 메모이제이션

import java.util.Scanner;


public class BOJ9461 { //정확도 오류

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] memo = new long[101];

        //2. for문으로 해결
        //if로 넣으면 i=1~5 값 할당이 안됨
        memo[1] = memo[2] = memo[3] = 1;
        memo[4] = memo[5] = 2;

        for (int i = 6; i <= 100; i++) {
            memo[i] = memo[i - 1] + memo[i - 5];
        }

        System.out.println(memo[n]);
        }
    }
Java
복사

일반 재귀로 풀고자 했으나 시간초과로 인해 for문 + 메모이제이션 기법을 활용.

•

접근방법 2. 일반 재귀

점화식 : f(n) = f(n-1) + f(n-5) (단, f>5)

import java.util.Scanner;

//파도반 수열 : 
public class BOJ9461 {
    static long padoban(int x) {
        if (x <= 3 ) {
            return 1;
        } else if (x <= 5) {
            return 2;
        } else {
            return padoban(x - 1) + padoban(x - 5);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.println(padoban(n));
    }
}
Java
복사

import java.util.Scanner;

//파도반 수열 : 시간초과
public class Main {
    static long padoban(int x) {
        if (x <= 3 ) {
            return 1;
        } else if (x <= 5) {
            return 2;
        } else {
            return padoban(x - 2) + padoban(x - 3);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.println(padoban(n));
    }
}
Java
복사