[백준] 17175번 : 피보나치는 지겨웡~ – JAVA [자바]

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

17175번: 피보나치는 지겨웡~

 

---

• 문제

 

---

• 문제 풀이

백준 17175번 피보나치는 지겨웡~은 이전에 많이 풀어봤던 피보나치 문제이다. 이 문제 역시 DP를 이용해서 풀 수 있다.

 

이 문제에서는 피보나치 함수가 다음과 같이 주어졌다.

 

int fibonacci(int n) { // 호출
  if (n < 2) {
    return n;
  }  
  return fibonacci(n-2) + fibonacci(n-1);
}

 

그리고 이 피보나치 함수에 인자로 입력되는 정수 n이 주어졌을 때 이 피보나치 함수가 몇 번 호출되었는지를 구하면 된다.

 

예시를 한 번 보겠다.

n = 0 : n이 0일 때 fibonacci(0)이 호출되고 n이 반환된다. 따라서 1번 호출된다.

 

n = 1 : n이 1일 때 fibonacci(1)이 호출되고 n이 반환된다. 따라서 1번 호출된다.

 

n = 2 : fibonacci(2)가 호출되고 fibonacci(1)과 fibonacci(0)도 호출된다. 따라서 총 3번 호출된다.

 

n = 3 : fibonacci(3)이 호출되고 fibonacci(2)와 fibonacci(1)이 호출된다. 따라서 1 + fibonacci(2) + fibonacci(1) = 1 + 3 + 1 = 5번 호출된다.

 

n = 4 : fibonacci(4)가 호출되고 fibonacci(3)과 fibonacci(2)가 호출된다. 따라서 1 + fibonacci(3) + fibonacci(2) = 1 + 5 +3 = 9번 호출된다.

 

여기서 패턴이 있다. n이 주어지면 우선 fibonacci(n)이 호출되고 그다음에 fibonacci(n-2)와 fibonacci(n-1)가 호출된다. 따라서 다음과 같은 점화식을 쓸 수 있다. 

 

dp [n] = 1 + dp [n-1] + dp [n-2]

 

dp는 1차원 int형 DP 테이블이라고 하고 dp에는 n이 주어졌을 때 몇 번의 피보나치 함수가 호출되었는지를 저장하겠다.

 

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main{
    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[51];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (1 + dp[i-1] + dp[i-2]) % 1000000007;
        }
        System.out.print(dp[n]);
    }
}

 

 

---

• 후기

되게 쉬운 피보나치 DP 문제였던 거 같다.