[C++] 백준 1003번 피보나치 함수

시간 제한과 문제를 보더라도 쉽게 알 수 있는 다이나믹 프로그래밍 문제였다.

다이나믹 프로그래밍의 Bottom Up 방식으로 문제를 접근했다.

F[0] = 1 0

F[1] = 0 1

F[2] = 1 1

F[3] = 1 2

.

.

.

즉, An = A(n-1) + A(n-2)임을 알 수 있다.

 

코드 전문

먼저 테스트 케이스 변수, 입력받는 정수 n이 있다.

그리고 pair<> 자료형의 배열을 사용해서 각 수마다 0이 나오는 횟수와 1이 나오는 횟수를 저장했다.

pair 자료형은

1. {A, B}의 형태로 입력할 수 있다.
2. make_pair(A, B)의 형태로도 입력할 수 있다.
3. 첫번째는 first, 두번째는 second의 형태로 접근한다.

0과 1은 알 수 있으므로 미리 배열에 입력해 놓는다.

각 테스트 케이스마다 n을 입력받고 반복문을 돌면서 dp 배열을 원하는 정수 n까지 업데이트 시킨다.

결과를 출력한다.

다이나믹 프로그래밍이란 것을 알았다면 쉽게 풀 수 있었던 문제였다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인 가능하다.