반응형
https://www.acmicpc.net/problem/2748
피보나치 수를 구하는 문제.
문제를 보면 처음 들어야할 생각은 동적 계획법(dynamic programing)를 떠올려주면 쉽게 풀린다.
재귀로 구현하면 아마 시간초과가 걸릴것이다.
그렇기 때문에 dp 배열을 이용하여 각 값을 저장해주고 다음 값을 구할때 계산하는 대신 앞에 계산한 값을 가져와주면 된다. 현재 값은 그 전의 값 + 그 전전 값 이 식을 구현해 주면 된다.
그리고 dp배열 선언할때 int로 선언하면 범위가 초과 되기 때문에 long long으로 해주었다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
long long dp[91]; // 범위 초과 방지
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2]; // 그 전 값 + 그 전전 값
}
cout << dp[n];
return 0;
} // dynamic programing
|
cs |
사용 알고리즘 : dynamic programing(동적 계획법)
yea!
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 2217 로프 c++ [컴공과고씨] (2) | 2022.03.24 |
---|---|
백준 1758 알바생 강호 c++ [컴공과고씨] (0) | 2022.03.24 |
백준 2636 치즈 c++ [컴공과고씨] (0) | 2022.03.21 |
백준 1697 숨바꼭질 c++ [컴공과고씨] (0) | 2022.03.21 |
백준 6593 상범빌딩 c++ [컴공과고씨] (0) | 2022.03.21 |