[백준 1003번 문제, JAVA] 피보나치 함수

문제

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int[][] lists = new int[41][2];
        lists[0] = new int[]{1, 0};
        lists[1] = new int[]{0, 1};

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

        int n = Integer.parseInt(br.readLine());
        final StringBuilder sb = new StringBuilder();

        for(int i=0; i<n; i++) {
            int k = Integer.parseInt(br.readLine());
            sb.append(lists[k][0]).append(" ").append(lists[k][1]).append("\n");
        }

        System.out.println(sb);
        br.close();
    }
}

---

해결

내 수준에 맞는 문제가 여기있구나 ㅠㅠㅠㅠ 다른건 너무 어려웠는데 이건 풀만하네

 

피보나치 수열은 이런건데 문제에 재귀호출로 만든 함수를 알려준다

근데 그걸 쓰면 시간초과 에러가 난다

 

처음에는 메모리 초과 오류가 나길래 ArrayList를 없애고 그냥 배열로 했는데 시간 초과 에러가 나서

이걸 쓰면 안되는구나 싶었다

 

그래서 예전에 뭐 어떨때는 재귀보단 그냥 쓰는게 더 낫다는게 기억났다

근데 피보나치수열을 그냥 쓰는건 상관없는데

0이 몇개고 1이 몇개인지 어케아느냐에서 좀 고민했는데

 

 

앞에 0은 0을 1번, 1은 1을 1번 호출한다

이걸 미리 배열로 만들어놓고

2번째 오는 1은 앞에서 두번째의 0에서 (0을 1번 호출, 1은 0번) 앞에서 첫번째의 1에서 (0을 1번, 1을 1번) 호출한 것을 각각 더해서 넣게 되면 1, 2를 배열에 넣을 수 있다

 

나머지 뒤에것도 앞에서 두번째의 배열과 앞에서 첫번째의 배열의 각 인덱스의 값을 더하면 0과 1을 몇번 호출하는지 구할 수 있었다...

 

 

단 세번만에!! 기쁨의 세레모니~

---

참고

링크