[백준 BOJ] 2748번 피보나치 수 2 (C++/cpp)

문제 설명

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

2748번: 피보나치 수 2

 

접근 방법 - 다이나믹 프로그래밍(DP) 기초 문제

백준의 2748번 문제는 다이나믹 프로그래밍(DP)의 원리를 이용한 기초 문제이다.

해당 문제는, 입력값에 대해 대응되는 피보나치 수의 값을 구하여 출력해야 하는 문제이다.

피보나치의 수가 DP의 가장 기본적인 문제라고 하는데, 사실 필자는 그 의견에 완전히 동의하지는 못하고 있다.

심지어 백준에는 이 DP의 가장 기초적인 원리를 다루고 있는 문제가 있는데, 이에 대한 문제 풀이 링크를 아래에 기재해놓았다.

이 알고리즘에 대해 어색하다면 아래의 글을 먼저 참고해볼 것을 권하고 싶다.

https://smary-it.tistory.com/m/223

[백준 BOJ] 13699번 점화식 (C++/cpp)

피보나치의 수에 대한 설명은 문제에 자세히 기재되어있으니 이를 참고해보길 바란다.

필자는 위 링크에 있는 것과 마찬가지로 배열을 만들어 각 피보나치 수의 값을 저장하도록 하였다. 

(메모이제이션이라는 개념과 연관이 깊으며, 이에 대한 것은 추후에 글로 다루어볼 예정이다.)

다만 여기에선, 이미 연산된 값을 필요로 할 때엔 연산을 다시 수행하지 않고 이미 저장된 값을 불러와 실행시간을 단축시키도록 하였다.

더 자세한 해설은 아래에 기재해놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 피보나치 수의 값을 저장할 배열(mem)을 전역 변수로 선언해둔다.

(여기서 최대 입력값을 고려해보았을 때, 숫자가 int형의 범위가 넘어갈 수 있기 때문에 long long int형으로 선언해둔다.)

 

2) 값(n)을 입력받는다.

 

3) n에 대하여 함수를 실행하여 아래의 연산을 취하도록 한다.

(아래에는 재귀 함수의 실행 순서에 대하여 기술되어있다.)

(이때, 반환값이 int형의 범위를 넘어설 수 있기 때문에 반환형을 long long int형으로 설정해둔다.)

- 만일 현재 값이 1 또는 2라면, 피보나치 수에 있어 해당 값에 대응하는 숫자는 1이기 때문에 1을 반환한다.

- 만일 1 또는 2가 아니라면, 피보나치 수의 규칙에 따라 숫자를 구하여 mem의 현재 인덱스에 저장하도록 한다.

이때 재귀를 이용하는데, 필요한 피보나치 수의 값이 mem에 따로 저장된 것이 있다면 이를 반환하도록 한다.

- 위 과정을 통해, 최종적으로 입력값 n에 대한 피보나치 수를 반환하도록 한다.

 

4) 위에서 출력을 완료하였다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 2748번 코드
long long int mem[91];

long long int fibo(int n) {
	if (n == 1 || n == 2) {
		return 1;
	}
	if (mem[n] != 0) {
		return mem[n];
	}
	mem[n] = fibo(n - 1) + fibo(n - 2);
	return mem[n];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	cout << fibo(n) << endl;
}

 

제출 결과

(2022.05.19 백준 2748번 문제 제출 결과)