[BOJ/DP] 백준 1003 - 피보나치 함수 / 2748 - 피보나치 수 2 / 1788 - 피보나치 수의 확장 (Java)

1003 - 피보나치 함수 

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

문제

fibo(3): fibo(2), fibo(1) (첫 번째 호출)
1. fibo(2): fibo(1) (두 번째 호출), fibo(0)
1) fibo(1) (두 번째 호출): 1 출력, 1 return
2) fibo(0): 0출력, 0 return
=> fibo(2): fibo(1), fibo(0) 결과 얻고, 1 return
2. fibo(1) (첫 번째 호출): 1출력, 1 return

=> fibo(3): fibo(2), fibo(1) 결과 얻고, 2 return 
1은 2번 출력, 0은 1번 출력

=> N이 주어졌을 때, fibo(n) 호출했을 때 0과 1이 각각 몇 번 출력?

입력
첫째 줄: 테스트 케이스 개수 T
각 테스트 케이스는 한 줄로 이뤄져 있고, N 주어짐 (N (0 or 자연수) <= 40)
출력: 각 테스트 케이스마다 0이 출력되는 횟수, 1이 출력되는 횟수 (공백 구분)

---

풀이

• `dp[i] = dp[i - 1] + dp[i - 2]`

 

•  fibo(0)
  • 0의 개수: dp[0][0] = 1
  • 1의 개수: dp[0][1] = 0
• fibo(1)
  • 0의 개수: dp[1][0] = 0
  • 1의 개수: dp[1][1] = 1

---

코드

import java.io.*;

// 피보나치 함수
public class boj_1003 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int[][] dp = new int[41][2];
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;

        for (int i = 2; i <= 40; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
            dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
        }

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

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N][0] + " " + dp[N][1]).append('\n');
        }

        System.out.println(sb);
    }
}

---

2748 - 피보나치 수 2 

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

문제

피보나치 수는 0과 1로 시작
0번째 피보나치 수: 0/ 1번째 피보나치 수: 1
2번째부터는 바로 앞 두 피보나치 수의 합
-> $F_n = F_{n-1} + F_{n-2} (n >= 2)$

=> n이 주어졌을 때 n번째 피보나치 수?

입력: 첫째 줄에 n이 주어짐 (n (자연수) <= 90)
출력: n번째 피보나치 수

---

풀이

• `dp[i] = dp[i - 1] + dp[i - 2]`
• `dp[0] = 0`, `dp[1] = 1`

 

주의:` long[] dp = new long[91];`

=> `int` 범위 초과할 수 있기 때문에 `long`

---

코드

import java.io.*;

// 피보나치 수 2
public class boj_2748 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        long[] dp = new long[91];
        dp[0] = 0;
        dp[1] = 1;

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

        System.out.println(dp[n]);
    }
}

---

1788 - 피보나치 수의 확장

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

문제

피보나치 수 f(n)을 음수인 경우로도 확장
ex. n = 1일 때 f(1) = f(0) + f(-1) => f(-1) = 1

=> n이 주어졌을 때, 피보나치 수 f(n)?

입력: 첫째 줄에 n (n의 절댓값 < 1,000,000)
출력
첫째 줄: f(n): 양수 -> 1 / 0 -> 0 / 음수 -> -1
둘째 줄: f(n)의 절댓값 % 1,000,000,000 

---

풀이

`f(n) = f(n - 1) + f(n - 2)` (n >= 2)

-> n = 2, f(2) = f(1) + f(0)

=> `f(n - 2) = f(n) - f(n - 1)`: 음수 점화식

 

f(0) = 0, f(1) = 1

• f(-1) = f(1) - f(0) = 1 - 0 = 1
• f(-2) = f(0) - f(-2) = 0 - 1 = -1
• f(-3) = f(-1) - f(-2) = 1 - (-1) = 2
• f(-4) = f(-2) - f(-3) = -1 - 2 = -3
• f(-5) = f(-3) - f(-4) = 2 - (-3) = 5

=> 짝수 음수 -> 부호 음수

 

주의:` long[] dp = new long[1_000_001];`

=> `int` 범위 초과할 수 있기 때문에 `long`

---

코드

import java.io.*;

// 피보나치 수의 확장
public class boj_1788 {
    static final int MOD = 1_000_000_000;

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

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

        if (n < 0 && n % 2 == 0) sb.append(-1).append("\n");
        else if (n == 0) sb.append(0).append("\n");
        else sb.append(1).append("\n");

        n = Math.abs(n);
        long[] dp = new long[1_000_001];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        sb.append(dp[n]);
        System.out.println(sb);
    }
}