[알고리즘/백준] 2747번 : 피보나치 수(Java)

문제	2747번 : 피보나치 수
문제링크	https://www.acmicpc.net/problem/2747
난이도	B2
언어	Java
분류	수학, 구현, 다이나믹 프로그래밍

 

 

📌 최종 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 피보나치 수 입력
        int n = Integer.parseInt(br.readLine());

        bw.write(String.valueOf(fn(n)));

        bw.flush();
        bw.close();
    }

    public static int fn (int n) {
        // 0 or 1일 경우 바로 반환
        if ( n <= 1 ) {
            return n;
        }

        // 피보나치 초기값 설정
        int a = 0; // n-2
        int b = 1; // n-1

        int value = 0;

        // 2~n항 계산
        for (int i = 2; i <= n; i ++) {
            value = a + b;  // 현재 항 = 이전 두 항 합
            a = b;          // 다음 계산을 위해 값 이동
            b = value;      // // 다음 계산을 위해 값 이동
        }
        return value;
    }
}

📌 구해야 하는 정답

- n번째 피보나치 수

📌 풀이하기

1. 입력받기

int n = Integer.parseInt(br.readLine());

 

2. 계산

public static int fn (int n) {
    // 0 or 1일 경우 바로 반환
    if ( n <= 1 ) {
        return n;
    }

    // 피보나치 초기값 설정
    int a = 0; // n-2
    int b = 1; // n-1

    int value = 0;

    // 2~n항 계산
    for (int i = 2; i <= n; i ++) {
        value = a + b;  // 현재 항 = 이전 두 항 합
        a = b;          // 다음 계산을 위해 값 이동
        b = value;      // // 다음 계산을 위해 값 이동
    }
    return value;
}

 

3. 결과 출력하기

bw.write(String.valueOf(fn(n)));

 

📌 시간 복잡도

DP 배열을 탐색하는 시간복잡도를 구해봅시다.

점화식을 계산하는데에는 단순 상수연산이 소요됩니다 → O(1)

이를 총 N개에 대해 탐색하므로, 최종 시간복잡도는 O(N)이 됩니다.

 

N은 최대 45이므로 시간제한 1초안에 충분히 가능한 연산 개수 입니다.

 

📌 코드 설계

1. 문제의 input을 받습니다.
2. DP 배열을 초기화 하고 가장 작은 답을 구합니다.
3. 세운 점화식에 맞게 dP 배열을 탐색합니다.
4. 정답을 출력합니다.