13270 백준 피보나치 치킨

문제

문제 분석

i번째 피보나치 수열을 저장하는 배열을 DP[i]라고 하자.

예시를 보면 알겠지만, 인원수와 닭 수 모두 피보나치 수열의 형태를 띄고, DP[i]인 DP[i-1]형태를 띈다.

문제는 이것을 이용해서 어떻게 최대, 최소를 구할까?... 인데

이 문제에서 가장 마음에 들지 않았던 부분은 N을 정확하게 명시하지 않았았다는 점이었다. N이 제대로 명시되지 않았기 때문에 어느정도의 복잡도를 가져도 되는지 정확하게 파악하지 못했고, DP보다는 수학적으로 접근하려고 시도했었다. (뭐 대충 3천정도라 하는데 이걸 어케알아 ㅋㅋ)

그래서 수학적으로 최소는 구해보았는데, DP[i] = DP[i-1] + DP[i-2]이고 DP[i-1] / DP[i]의 비율이 가장 낮은 경우의 수들을 골라야 한다.  DP[i-1] / DP[i] = DP[i-1] / (DP[i-1]+DP[i-2])이다. DP[1] 과 DP[0]을 제외하곤 DP[i-1] > DP[i-2]이므로 N=2일때의 비율이 0.5로 최소임을 알 수 있다.

이렇게 홀수일 때는 3인 2마리 세트를 1개만 넣고, 나머지를 2인 1세트로 채우면 이 수가 최소일 것이다.

최대는 아무리 생각해도 안되길래 그냥 DP로 풀었다.

DP_2[i]를 i인일 때 만들어 낼 수 있는 최대 치킨수 라고 정의하면, DP_2[i] = DP_2[k] + DP_2[i-k]의 최대를 찾으면 된다.

k는 반드시 피보나치 수열의 규칙을 따를 것이므로 k의 경우의 수는 N이 3천이라고 가정할 때 대충 최대 30정도밖에 안될것이다.

러프하게 보았을 때 3000 * 30 < 10^5이므로 복잡도 상으로는 문제 없을것이므로 이를 이용하면 올바르게 구해낼 수 있을 것이다.

 

 

 

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;
int dp[1000000] = {0};
int dp_2[1000000] = {0};

void solution()
{
    // code
    int n;
    cin >> n;
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    int now_idx = 2;
    while(dp[now_idx] <= n)
    {
        ++now_idx;
        dp[now_idx] = dp[now_idx-1] + dp[now_idx-2];
    }
    int min_output = 0;
    int max_output = 0;
    int tmp_c = n;
    if(tmp_c % 2 == 1)
    {
        tmp_c -= 3;
        min_output += 2;
    }
    min_output += tmp_c/2;
    tmp_c = n;
    dp_2[2] = 1;
    dp_2[3] = 2;
    dp_2[4] = 2;
    dp_2[5] = 3;
    dp_2[6] = 4;

    for(int i=7; i<=n; i++)
    {
        int now_max = -1;
        int tmp_idx = 2;
        while(dp[tmp_idx] <= i)
        {
            now_max = max(now_max, dp_2[dp[tmp_idx]] + dp_2[i - dp[tmp_idx]]);
            tmp_idx++;
        }
        dp_2[i] = now_max;
    }
    cout << min_output << " " << dp_2[n];
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

 

인터넷에 더 찾아보니 fib(i)/fib(i-1)에서 i가 무한으로 늘어날 때 나타나는 값이 Golden ration라고 하는 값에 수렴한다고 한다. (약 1.618034) 그리고 i가 커질수록 이 값이 무조건 작아지는게아니라 왔다갔다하는거라 DP로만 풀 수 있지 않을까? 라고 생각했는데 푼사람들 코드르 보면서 흥미로운 점화식 하나를 발견했다.

최소 : (N + 1) / 2, 최대 : (N * 2 / 3)

최소는 내가 푼 방식의 연장선일것이고 (어차피 N이 홀수라서 3을 섞으면 2이므로) 최대는 아무리봐도 모르겠다.

수학과 친구한테 물어봐야징

-> 피보나치 두 수의 비가 황금비로 가고 그 수렴성은 2/1이 가장 크고 3/2가 가장 작다고한다.

그렇기 때문에 위처럼 풀 수 있는것이다 ㅋㅋ