1003번 피보나치 함수(DP)

#문제링크 : https://www.acmicpc.net/problem/1003

<전략>

1. 피보나치 수가 아니고, 피보나치 수 중 몇 번째에 있는 수인지를 묻는 것이므로, 2번째에 있는 피보나치 수는 0번째에 있는 피보나치 수와 1번째에 있는 피보나치 수의 합과 같다.

2. 2번째에 있는 피보나치 수의 0번째 수와 1번째 수의 호출 수는 각각 1번씩으로 (0번째 호출수, 1번째 호출수)로 표현하면 (1,1)이다. 3번째에 있는 피보나치 수의 0번째 수와 1번째 수의 호출 수는 3(번째) = 2(번째) + 1(번째) 이므로 2번째가 (1,1) 이었고, 1번째가 (0,1)이므로 3번째 = (1, 1) + (0, 1) = (1, 2) 가 된다.

3.  N번째에 있는 수가 0번째 수와 1번째 수를 각각 몇번씩 호출하는지를 알기 위해서는 N-1번째수와 N-2번째수가 각각 호출한 0번째, 1번째수를 따로따로 더해주면 된다.

4. 위의 과정을 이중배열 num[N][2]나 pair<int, int> num[N]배열을 이용해서 N번째에 있는 수가 0번째와 1번째 수를 몇번씩 호출하는지 저장해놓고 N보다 큰 수가 호출되면 저장해놓은 수를 더해주기만 해서 구할 수가 있다.

Code