210115 | 백준 동적계획법 1003 | C++
동적계획법
전체 문제를 작은 문제로 단순화한다. -> 부분 문제를 정의한다.
재귀적인 구조를 활용할 수 있는 점화식을 만든다. -> 점화식을 만든다.
작은 문제를 해결한 방법으로 전체 문제를 해결한다. -> 문제를 해결한다.
전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식
1003
#include <iostream>
using namespace std;
int fibo[50] = { 0, 1, };
int fibonacci(int n) {
if (n == 0) {
return fibo[n];
}
else if (n == 1) {
return fibo[n];
}
if (fibo[n] != 0)
return fibo[n];
else {
return fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main() {
int T;
cin >> T;
int temp;
for (int i = 0; i < T; i++) {
cin >> temp;
if (temp == 0)
cout << "1 0" << '\n';
else
cout << fibonacci(temp - 1) << " " << fibonacci(temp) << '\n';
}
}
🎈 배열 초기화
0과 1 인덱스에 각각 피보나치 수열함수를 불러올때마다 더해질 0와 1을 저장한다. {0, 1, } 은 인덱스 0에 0, 인덱스 1에 1을 저장하고, 그 뒤에는 0으로 모두 초기화한다는 뜻이다.
🎈 피보나치 수열함수
int fibonacci(int n) {
if (n == 0) {
return fibo[n];
}
else if (n == 1) {
return fibo[n];
}
if (fibo[n] != 0)
return fibo[n];
else {
return fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
}
만약 n이 0이면 인덱스 0을 리턴하고, n이 1이면 인덱스 1을 리턴하여 결과리턴값에서 각 int값이 더해지도록 구현한다.
🎈 메인 함수
int main() {
int T;
cin >> T;
int temp;
for (int i = 0; i < T; i++) {
cin >> temp;
if (temp == 0)
cout << "1 0" << '\n';
else
cout << fibonacci(temp - 1) << " " << fibonacci(temp) << '\n';
}
temp가 0일때는 피보나치 수열 합의 결과값이 0이므로 1 0을 출력하도록한다.
그 외의 경우에서는 규칙성을 찾아보았을 때, 0을 출력하는 횟수는 fibonacci(temp - 1), 1을 출력하는 횟수는 fibonacci(temp)에 해당한다.
#include <iostream>
using namespace std;
int fibo[50] = { 0, 1, };
int fibonacci(int n) {
if (n == 0) {
return fibo[n];
}
else if (n == 1) {
return fibo[n];
}
if (fibo[n] != 0)
return fibo[n];
else {
return fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main() {
int T;
cin >> T;
int temp;
for (int i = 0; i < T; i++) {
cin >> temp;
if (temp == 0)
cout << "1 0" << '\n';
else
cout << fibonacci(temp - 1) << " " << fibonacci(temp) << '\n';
}
}
🎈 배열 초기화
0과 1 인덱스에 각각 피보나치 수열함수를 불러올때마다 더해질 0와 1을 저장한다. {0, 1, } 은 인덱스 0에 0, 인덱스 1에 1을 저장하고, 그 뒤에는 0으로 모두 초기화한다는 뜻이다.
🎈 피보나치 수열함수
int fibonacci(int n) {
if (n == 0) {
return fibo[n];
}
else if (n == 1) {
return fibo[n];
}
if (fibo[n] != 0)
return fibo[n];
else {
return fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
}
만약 n이 0이면 인덱스 0을 리턴하고, n이 1이면 인덱스 1을 리턴하여 결과리턴값에서 각 int값이 더해지도록 구현한다.
🎈 메인 함수
int main() {
int T;
cin >> T;
int temp;
for (int i = 0; i < T; i++) {
cin >> temp;
if (temp == 0)
cout << "1 0" << '\n';
else
cout << fibonacci(temp - 1) << " " << fibonacci(temp) << '\n';
}
temp가 0일때는 피보나치 수열 합의 결과값이 0이므로 1 0을 출력하도록한다.
그 외의 경우에서는 규칙성을 찾아보았을 때, 0을 출력하는 횟수는 fibonacci(temp - 1), 1을 출력하는 횟수는 fibonacci(temp)에 해당한다.
Author And Source
이 문제에 관하여(210115 | 백준 동적계획법 1003 | C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nayeon_p00/210115-백준-동적계획법-1003-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)