백준 3일차 : 백준 1003번 피보나치 함수

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

1003번: 피보나치 함수

 

 

정말.. 어려웠어요..ㅠㅠ

0.25초라는 시간제한때문에 일반적으로 풀면 안되고 DP를 사용해야 하더라고요!

저는 이 문제 공부하면서 DP에 대해서 처음 배웠어요 이렇게 성장하는 거겠죠..!

 

DP가 간단하게 말하면, 전에 사용했던 값이 있다면 이를 저장. 재사용해서 탐색 시간을 많이 줄이는 방법인 것 같아요!

저도 자세히는 모르겠지만.. 틀렸다면 말해주세요~!

 

저도 처음에는 그냥.. 평범한 피보나치겠거니하고 재귀를 맘껏 돌려서 했더니 무조건 시간초과 뜨더라고요..!

 

배열을 사용해서 전에 사용했던 값을 하나하나 다 저장해서 새로운 값을 구할때 한번만의 연산으로 구할 수 있도록 했어요

 

거기다 입력이 40과 같거나 작은 수라고 해서 이를 미리 채워두고, 값을 출력할 때는 배열에서 바로 가져올 수 있게 했습니다

 

알고리즘을.. 전처럼 짜긴 짰지만 이대로 풀면 무조건 시간초과니까..!

문제가 이해 안되시는 분들만 보시고 코드짜실 땐 참고하시면 안 될 것 같아요 ㅎㅎ

 

 

수많은 시간초과와.. 수많은 입력 오류와 오타와 등등..의 연산을 해치고 성공했습니다..ㅎㅎ

그리고 저 3연속 틀렸습니다는.. 이상하게 참조를 해서 1을 넣었을때 오류가 났더라고요..

그것도 모르고 모범답안이랑 1~40까지 하나하나 비교해보고.. 그랬어요

저 첫번째 맞았습니다..는 ㅋㅋ 모범답안을 의심하고 뭔가 테스트케이스가 바뀐게 아닐지 넣어본.. 결과랍니다..^^

항상 이렇게 기본적인 것에서 많이 실수를 하는것 같아요😂😂

 

그럼 전 4일차로 돌아올게요!! 빠잉

 

 

 

작성 코드

---

import java.io.*;
import java.util.Arrays;
 
 
public class B1003 {
    
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        
        //N은 무조건 40보다 작다고 해서 배열을 미리 채워두기
    
        int[] zero=new int[41];
        Arrays.fill(zero, -1);
        zero[0]=1;
        zero[1]=0;
        int[] one=new int[41];
        Arrays.fill(one, -1);
        one[0]=0;
        one[1]=1;
        
        // 배열이 완성되어있지 않을 때(즉 값이 -1)만 k-1,k-2 값을 더해 배열을 채우기
        
        for(int k=0;k<41;k++) {
            if(zero[k]==-1) {
                zero[k]=zero[k-1]+zero[k-2];
            }
            if(one[k]==-1) {
                one[k]=one[k-1]+one[k-2];
            }
        }
        
        
        //실제 값 구할 때는 n-1+n-2만 더하기
        
        int n=Integer.parseInt(br.readLine());
        String[] result=new String[n];
        
        for(int i=0;i<n;i++) {
            int input=Integer.parseInt(br.readLine());
            if(input==0) result[i]="1 0";
            else if(input==1) result[i]="0 1";
            else {
                result[i]=(zero[input-1]+zero[input-2])+" "+(one[input-1]+one[input-2]);
            }
            
        }
        
        for(int l=0;l<n;l++) {
            System.out.println(result[l]);
        }
        
    }
 
}