1R/2016 10 12

오늘의 문제

• 함수
• [1]
• [2]

참가자

• 15이원준
• 박인서

코드

15이원준

피보나치 함수

#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]);
  }
}

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;
}

연속합

#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;
}

박인서

피보나치 함수

#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;
}

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;
}

연속 합

#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;
}

아이디어

15이원준

피보나치 함수

• 결국 각 수에 대한 0과 1이 나타는 수를 피보나치와 같이 더해주면 된다.

RGB 거리, 연속합

• 생략

15이원준

피보나치 함수

• 원준이의 아이디어와 유사

RGB 거리

• R[i] : max(G[i-1], B[i-1])+현재 R값
• G[i] : max(R[i-1], B[i-1])+현재 G값
• B[i] : max(R[i-1], G[i-1])+현재 B값

연속합

• hap[i-1]<0 ? hap[i]=a[i] : hap[i]=hap[i-1]+a[i];