[자바] 백준 10870번 피보나치 수 5, 2748번 피보나치 수 2

 

1. 10870번 피보나치 수 5

 

https://www.acmicpc.net/problem/10870

 

[문제 이해]

피보나치 수를 어떻게 동적 프로그래밍으로 구현하는지 알고만 있다면 어렵지 않은 문제였다. 배열을 N보다 하나 크게 만들어서 0은 무시하고 인덱스 1번부터 원하는 값을 넣을 수 있도록 구현하였다.

 

[문제 풀이]

1 이나 2 면 1을 넣고 다른 값이면 i-1과 i-2번째 인덱스의 값을 더해서 넣을 수 있도록 구현했다.

 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N+1];
        arr[0] = 0;

        for(int i = 1; i < N+1; i++){
            if(i == 1 || i == 2){
                arr[i] = 1;
            }
            else{
                arr[i] = arr[i-1] + arr[i-2];
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(arr[N]));
        bw.flush();
        bw.close();
    }
}

 

 

2. 2748번  피보나치 수 2

 

https://www.acmicpc.net/problem/2748

 

[문제 이해]

위랑 동일한 문제인 줄 알고 비슷하게 구현해서 돌려봤는데 틀렸다고 하길래 반례를 찾아.. 여러가지를 넣다가 가장 마지막인 90을 넣었을 때 마이너스 값이 나오는 것을 발견했다. 아.. int 말고 Long으로 풀어야 되는 문제구나..

 

[문제 풀이]

Long으로 타입을 변경해서 위와 동일하게 풀면 되는 문제였다. Long은 어떻게 BufferedWriter로 출력할 때 변환하는지 몰라서 이 부분은 조금 외워둬야겠다..

import java.io.*;
import java.util.*;

public class Main {

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

        Long N = Long.parseLong(br.readLine());
        Long[] arr = new Long[(int) (N+1)];
        arr[0] = 0L;
        arr[1] = 1L;

        for(int i = 2; i < N+1; i++){
            arr[i] = arr[i-1] + arr[i-2];
        }
        bw.write(String.valueOf(arr[Math.toIntExact(N)]));

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