3.1.1. 피보나치 함수 ¶
#include<iostream> #include<utility> using namespace std; int arr[41][2] = { 0, }; pair<int,int> search(int num){ if(arr[num][0] + arr[num][1]){ return make_pair(arr[num][0], arr[num][1]); } pair<int,int> tmp1 = search(num-1); pair<int,int> tmp2 = search(num-2); arr[num][0] = tmp1.first + tmp2.first; arr[num][1] = tmp1.second + tmp2.second; return make_pair(arr[num][0], arr[num][1]); } int main(){ arr[0][0] = arr[1][1] = 1; int T; cin>>T; while(T--){ int n; cin>> n; search(n); printf("%d %d\n", arr[n][0],arr[n][1]); } }
3.1.2. RGB 거리 ¶
#include<iostream> #include<algorithm> using namespace std; int arr[1001][3] = {0,}; int w[1001][3] = {0,}; int main(){ int n; cin>>n; for(int i = 0; i<n; i++){ for(int j = 0; j<3; j++){ scanf("%d", &w[i][j]); } } arr[0][0] = w[0][0]; arr[0][1] = w[0][1]; arr[0][2] = w[0][2]; for(int i = 1; i<n; i++){ arr[i][0] = min(arr[i-1][1] + w[i][0], arr[i-1][2] + w[i][0]); arr[i][1] = min(arr[i-1][0] + w[i][1], arr[i-1][2] + w[i][1]); arr[i][2] = min(arr[i-1][0] + w[i][2], arr[i-1][1] + w[i][2]); } int tmp = min(arr[n-1][0],arr[n-1][1]); tmp = min(tmp,arr[n-1][2]); cout<<tmp<<endl; }
3.1.3. 연속합 ¶
#include<iostream> #include<algorithm> #include<vector> using namespace std; int arr[100001]; int main(){ int n, ans; cin>> n; for(int i =0; i<n; i++){ int tmp; scanf("%d", &arr[i]); } ans = arr[0]; for(int i = 0; i<n;){ int sum = arr[i]; ans = max(ans, sum); int j; for(j = i+1; j<n; j++){ if(sum < 0){ sum = max(ans, sum); i = j; break; } sum += arr[j]; ans = max(ans, sum); } i = j; } cout<<ans<<endl; }
3.2.1. 피보나치 함수 ¶
#include <iostream> int main() { int t; std::cin>>t; while(t--){ int n; std::cin>>n; if(n==0){ std::cout<<"1 0\n"; continue; } int a=0,b=1; for(int i=1;i<n;i++){ int t=a+b; a=b; b=t; } std::cout<<a<<' '<<b<<std::endl; } return 0; }
3.2.2. RGB 거리 ¶
#include <iostream> #include <vector> struct rgb { int r, g, b; }; std::vector<rgb> c; rgb dp[1001]; int min(int x, int y) { return x > y ? y : x; } int main(){ int n; std::cin >> n; for (int i = 0; i < n; i++) { rgb t; std::cin >> t.r >> t.g >> t.b; c.push_back(t); } dp[0] = c[0]; for (int i = 1; i < n; i++) { dp[i].r = c[i].r + min(dp[i - 1].g, dp[i - 1].b); dp[i].g = c[i].g + min(dp[i - 1].r, dp[i - 1].b); dp[i].b = c[i].b + min(dp[i - 1].r, dp[i - 1].g); } std::cout << min(min(dp[n - 1].r, dp[n - 1].g), dp[n - 1].b); return 0; }
3.2.3. 연속 합 ¶
#include <iostream> #include <vector> std::vector<int> a,hap; int main() { int n; std::cin>>n; for(int i=0;i<n;i++){ int t; std::cin>>t; a.push_back(t); } hap.push_back(a[0]); for(int i=1;i<n;i++){ if(hap[i-1]<0) hap.push_back(a[i]); else hap.push_back(hap[i-1]+a[i]); } int res=hap[0]; for(int i=1;i<n;i++){ if(res<hap[i]) res=hap[i]; } std::cout<<res; return 0; }