반응형
문제 링크 : https://www.acmicpc.net/problem/2747
2309번: 일곱 난쟁이
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
www.acmicpc.net
문제
입력받은 n번째 피보나치 수를 구하는 문제
접근방식
여러가지 방법으로 풀어 봤다. 나이나믹 프로그래밍 기법 연습하고 싶어서, 탑다운 방식과 바텀업 방식 2가지로 풀어봤다.
탑다운 방식 코드
#include <iostream>
using namespace std;
int d[45] = { 0, };
int memo_fibo(int n)
{
if (n == 0) return 0;
else if (n == 1) return 1;
else if (d[n] != 0) return d[n];
d[n] = memo_fibo(n - 1) + memo_fibo(n - 2);
return d[n];
}
int main()
{
int N;
int fibo;
cin >> N;
fibo = memo_fibo(N);
cout << fibo << '\n';
return 0;
}
바텀업 방식
#include <iostream>
using namespace std;
int d[45] = { 0, };
int memo_fibo(int n)
{
d[0] = 1;
d[1] = 1;
for (int i = 2; i < n; i++)
{
d[i] = d[i - 1] + d[i - 2];
}
return d[n - 1];
}
int main()
{
int N;
int fibo;
cin >> N;
fibo = memo_fibo(N);
cout << fibo << '\n';
return 0;
}
이런 방식의 접근법은 처음 알게 되었는데, 알고리즘은 할수록 재밌는 방법들이 많다.
다른 문제의 코드 : https://github.com/DaeeYong/Algorithm-Solution-
DaeeYong/Algorithm-Solution-
Solution for Algorithm Problem. Contribute to DaeeYong/Algorithm-Solution- development by creating an account on GitHub.
github.com
반응형
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[C/C++]백준 1003번 - 피보나치 함수 (0) | 2021.07.29 |
---|---|
[C/C++] 백준 1463번 - 1로 만들기 (0) | 2021.07.28 |
[C/C++]백준 2440문제 - 별찍기 - 3 (0) | 2021.07.26 |
[C/C++]백준: 1924번 2007년 (0) | 2021.07.26 |
백준 2309번, 언어 : C/C++ (2) | 2021.07.04 |