[java]피보나치 함수 - 백준1003

문제

• 피보나치 함수(백준1003)

풀이

문제 해석을 하자면,

• 피보나치 함수는 정말 유명한데 이 피보나치 함수를 구현하면 된다.

풀이

• bottom-top 방식과
• top-bottom 방식을 구현해보았다.
• for문을 재귀로 또는 재귀를 for문으로 바꾸는것에 익숙해지자

코드

static int[][] dp = new int[44][2]; // 0횟수, 1횟수 를 구하기 위해 2차원 dp

//메모이제이션 연습
static int fib(int N, int j) {
    //메모이제이션
    if(dp[N][j]!=0) return dp[N][j];
    //base condition
    if(N==0) {
        if(j==0) return dp[N][0] = 1;
        if(j==1) return dp[N][1] = 0;
    }
    if(N==1) {
        if(j==0) return dp[N][0] = 0;
        if(j==1) return dp[N][1] = 1;
    }
    //recursion
    if(j==0) return dp[N][0] = fib(N-1,0)+ fib(N-2,0);
    if(j==1) return dp[N][1] = fib(N-1,1)+ fib(N-2,1);
    return -1;
}

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    for(int t=0; t<T; t++){
        int N = Integer.parseInt(br.readLine());
        // 임시로 -> bottom-top 주석처리
        //      //init dp 
        //      dp[0][0] = 1; dp[0][1] = 0;
        //      dp[1][0] = 0; dp[1][1] = 1;
        //      //dp
        //      for(int i=2; i<=N; i++) {
        //        dp[i][0] = dp[i-1][0] + dp[i-2][0];
        //        dp[i][1] = dp[i-1][1] + dp[i-2][1];
        //      }
        fib(N, 0);
        fib(N, 1);
        sb.append(dp[N][0]).append(" ").append(dp[N][1]).append("\n");
    }
    System.out.println(sb);
}

느낀점

생략