문제 링크입니다:https://www.acmicpc.net/problem/1003
algospot에서 동적계획법 문제를 풀다보니 아직 미흡한 것 같아서 백준 온라인 저지에서 동적계획법 기초 문제를 풀어봤습니다.
물론 동적계획법을 사용하지 않아도 되는 문제이지만 동적계획법을 연습하고자 메모이제이션을 사용하였습니다.
/*
N이 주어졌을 때, fibonacci(N)을 호출할 경우 0과 1이 각각 몇번 출력되는가?
*/
#include <iostream>
#include <cstring> //memset
using namespace std;
int N; //주어진 숫자
int save = 2; //이미 구한 수는 다시 구하지 않는다
int cache[2][41]; //메모이제이션
void fibonacci(int n)
{
if (N >= save)
{
for (int i = save; i <= N; i++)
{
cache[0][i] = cache[0][i - 1] + cache[0][i - 2];
cache[1][i] = cache[1][i - 1] + cache[1][i - 2];
}
save = N;
}
}
void initialize(void)
{
memset(cache, 0, sizeof(cache));
//피보나치수열을 위해서는 앞에 두개의 숫자가 필요하므로
cache[0][0] = 1;
cache[1][1] = 1;
}
int main(void)
{
int T; //test_case
cin >> T;
initialize();
for (int i = 0; i < T; i++)
{
cin >> N;
if (N > 40 || N < 0)
exit(-1);
fibonacci(N);
cout << cache[0][N] << " " << cache[1][N] << endl;
}
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1463번 1로 만들기 (0) | 2018.02.02 |
---|---|
백준 2579번 계단 오르기 (0) | 2018.02.02 |
백준 1932번 숫자삼각형 (2) | 2018.02.02 |
백준 1149번 RGB거리 (0) | 2018.02.01 |
백준 2133번 타일 채우기 (0) | 2018.01.28 |