안녕하세요! 테크지니어22입니다.
오늘은 백준 알고리즘 1003번 - 피보나치 함수 를 풀어보도록 하겠습니다.
https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
[문제 접근]
n = 2, n =3 , n= 4 .... 일 때 f(0)과 f(1)이 호출된 개수를 확인하면서 패턴이 있는지 계속 생각했습니다.
D[i] = D[i-2] + D[i-1] (i >= 2) 점화식을 발견하고 for문을 이용하여 bottom-up방식으로 점화식 값들을 채웠습니다.
[풀이 전략]
1. d[0],d[1] 초기값을 설정합니다.
2. 점화식, for문을 이용하여 d[i]의 값들을 구합니다.
3. 최종 d[n]의 값을 출력합니다.
[코드]
#include <iostream>
#include <algorithm>
using namespace std;
int t ;
int n ;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t ;
while (t--)
{
pair<int,int> d[41];
cin >> n ;
d[0] = {1,0};
d[1] = {0,1};
for(int i = 2 ; i <= n ; i++){
d[i] = {d[i-2].first + d[i-1].first, d[i-2].second + d[i-1].second };
}
cout << d[n].first << ' ' << d[n].second<<'\n' ;
}
}
[배울 점]
- i = 1, 2, 3 패턴을 찾아보고, i = k , i = k+1 ... 에서 패턴을 적용해서 성립여부 확인하기.
'알고리즘 > 백준' 카테고리의 다른 글
[백준/C++] 알고리즘 11727번 - 2×n 타일링 2 (0) | 2024.04.13 |
---|---|
[백준/C++] 알고리즘 1932번 - 정수 삼각형 (0) | 2024.04.13 |
[백준/C++] 알고리즘 3190번 - 뱀 (0) | 2024.04.11 |
[백준/C++] 알고리즘 2617번 - 구슬 찾기 (0) | 2024.04.10 |
[백준/C++] 알고리즘 20922번 - 겹치는 건 싫어 (1) | 2024.04.09 |