백준 2747번 문제

풀이

• 피보나치 수열 N번 째 구하는 문제
• 동적 계획법 중 대표적인 문제로 N[i - 2] + N[i - 1] 을 사용하면 손 쉽게 풀 수 있는 문제
• 내가 해결한 문제는 바텀-업에 가까움

import java.io.*;

public class 피보나치 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        long[] array = new long[n + 1];
        array[0] = 0; array[1] = 1;
        long result = array[0];
        if (n == 1) result = array[1];
        else if (n >= 2) {
            for (int i = 2; i <= n; i++) {
                array[i] = array[i - 1] + array[i - 2];
            }
            result = array[n];
        }
        bw.write(result + "");
        bw.flush();
        bw.close();
        bf.close();
    }
}

1. n-2 & n-1 번 째 초기화

int n = Integer.parseInt(bf.readLine());
long[] array = new long[n + 1];
array[0] = 0; array[1] = 1;
long result = array[0];
if (n == 1) result = array[1];
else if (n >= 2) {
    // 수열 구하기
}

• 수월한 계산을 위해 0(수열 n-2)번 째와 1(수열 n-1)번 째 초기화
• 해당 문제에선 n을 90까지 입력 받으니 int 타입이 아닌 long 타입으로 변수 선언
• n이 1 혹은 0 일 시, 해당 숫자로 변환, 그게 아니면 수열 구하기

2. 바텀-업 피보나치

for (int i = 2; i <= n; i++) {
    array[i] = array[i - 1] + array[i - 2];
}
result = array[n];

• 두 번째 부터 수열이 이어지므로 i를 2로 설정한 후 피보나치 수열 진행
• n번 째 숫자 도출만 원하니 결과 값은 반복문 끝난 후 결과 값 반환
• 톱-다운 방식은 주로 재귀함수를 이용하고 바텀-업은 주로 반복문 이용