백준 알고리즘: 1003번 피보나치 함수

문제 정보

---

 

1003번: 피보나치 함수

 

핵심

---

피보나치는 역시 DP(Dynamic Programming) 아닐까요?

피보나치의 특징인 f(n) = f(n-2) + f(n-1) 는 다음을 의미하기도 합니다

f(n)을 이루는 0의 개수와 1의 개수 = f(n-2)를 이루는 0의 개수와 1의 개수 + f(n-1)을 이루는 0의 개수와 1의 개수

따라서, 일반적인 피보나치 풀이처럼 풀되 0의 개수와 1의 개수를 더해가며 풀이하면 쉽게 풀이할 수 있을 것!

 

내 풀이의 경우 Fibo class를 만들어서, instance variable로 numberOfZero(0이 나타나는 개수)와 numberOfOne(1이 나타나는 개수) 를 추가해 주었고

f(0) = Fibo(1, 0) : 0은 1번, 1은 0번 나타남

f(1) = Fibo(0, 1) : 0은 0번, 1은 1번 나타남

를 먼저 추가시켜 주고, 특정 n의 f(n)이 구해져있지 않은 상태라면 n까지의 계산을 통해 값을 빠르게 구하고 이를 저장해 두어

다음 계산에 활용할 수 있었습니다

 

풀이

---

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

class Main {
    public static void main(String[] args) throws IOException {
        // (1, 0) (0, 1) (1, 1) (1, 2) (2, 3) (3, 5) (5, 8)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numberOfTestCases = Integer.parseInt(br.readLine());
        List<Fibo> dp = new ArrayList<>();
        dp.add(new Fibo(1, 0));
        dp.add(new Fibo(0, 1));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numberOfTestCases; i++) {
            int n = Integer.parseInt(br.readLine());
            if (n < dp.size())
                sb.append(dp.get(n).numberOfZero).append(" ").append(dp.get(n).numberOfOne)
                        .append('\n');
            else {
                int currentSize = dp.size();
                for (int index = currentSize; index <= n; index++) {
                    Fibo past2Node = dp.get(index - 2);
                    Fibo past1Node = dp.get(index - 1);
                    dp.add(new Fibo(past2Node.numberOfZero + past1Node.numberOfZero,
                            past2Node.numberOfOne + past1Node.numberOfOne));
                }
                sb.append(dp.get(n).numberOfZero).append(" ").append(dp.get(n).numberOfOne)
                        .append('\n');
            }
        }
        System.out.println(sb.toString());
    }
}


class Fibo {
    int numberOfZero;
    int numberOfOne;

    public Fibo(int numberOfZero, int numberOfOne) {
        this.numberOfZero = numberOfZero;
        this.numberOfOne = numberOfOne;
    }
}

 

Source Code on GitHub

---