[C++] 피보나치 치킨 (백준 13270번)

EDOC 2024-1 5회차 정모 (골드: 동적 계획법 알아보기 3) A

 

https://www.acmicpc.net/problem/13270

 

첫번째 풀이

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> minD(n + 1, 0);
    vector<int> maxD(n + 1, 0);

    minD[1] = maxD[1] = 0;
    minD[2] = maxD[2] = 1;

    if (n >= 3)
        minD[3] = maxD[3] = 2;
    
    int x1 = 2;
    int x2 = 3;
    while ((x1 + x2) <= n) {
        minD[x1 + x2] = maxD[x1 + x2] = minD[x2] + minD[x1];
        int tmp = x2;
        x2 = x1 + x2;
        x1 = tmp;
    }

    for (int i = 4; i < n + 1; i++) {
        minD[i] = minD[2] + minD[i - 2];
        maxD[i] = maxD[2] + maxD[i - 2];
        for (int j = 3; j < i - 1; j++) {
            minD[i] = min(minD[i], minD[j] + minD[i - j]);
            maxD[i] = max(maxD[i], maxD[j] + maxD[i - j]);
        }
    }

    cout << minD[n] << ' ' << maxD[n] << '\n';
}

그냥 무식하게 반복문 돌리면서 비교해서 푼 풀이이다. (정답)

 

두번째 풀이

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    int minC = 0;
    int maxC = 0;

    if (n % 6 == 0) {
        minC = n / 2;
        maxC = 2 * n / 3;
    }
    else if (n % 2 == 0) {
        minC = n / 2;
        maxC = 2 * (n - 2) / 3 + 1;
    }
    else if (n % 3 == 0) {
        minC = (n - 1) / 2 + 1;
        maxC = 2 * n / 3;
    }
    else {
        minC = (n - 1) / 2 + 1;
        maxC = 2 * (n - 2) / 3 + 1;
    }

    cout << minC << ' ' << maxC << '\n';
}

(정답)

 

일단 가능한 세트들을 적어보면 다음과 같다.

2인 1닭
3인 2닭
5인 3닭
8인 5닭

13인 8닭
21인 13닭

 

피보나치 수열에서는 어떤 수든 전부 2와 3으로 쪼갤 수 있다. 이 문제에서도 세트가 전부 피보나치 수로 이루어져있기 때문에 이러한 피보나치의 성질이 그대로 적용된다.
몇인이든 전부 2인 1닭 세트와 2인 3닭 세트로 구성할 수 있다. 이게 가능한 이유는 작은 세트들로 쪼개더라고 치킨 수는 유지가 된다는 피보나치의 성질 덕분이다. (예를 들어 8인 5닭 세트는 3인 2닭 세트와 5일 3닭 세트로 나누어도 치킨의 수는 동일하게 유지된다.)

이 때 2인 1닭의 개수를 최대화하면 치킨 수의 최솟값을 구할 수 있다. 3인 2닭의 개수를 최대화하면 치킨 수의 최댓값을 구할 수 있다. 

 

이 방법으로 풀게 되면 시간 복잡도가 무려 O(1)이다. n이 아무리 커도 상수 시간 안에 답을 구할 수 있는 강력한 풀이라는 것이다. 이 문제에서 n은 2016년에 재학 중이었던 카이스트 학생 수보다는 작거나 같은 2 이상의 정수이다. 찾아보니 현재 2024년 기준 카이스트의 재적 학생 수는 4912명이다. 아무튼 n은 10000보다는 작을 것이다. 10000까지는 두 가지 풀이 모두 잘 작동하지만, 100000만 되어도 첫번째 풀이로는 1분 이상은 걸리는 것 같다. 반대로 두번째 풀이로는 역시 똑같이 빠르게 나온다. 백준에서 시간을 비교하면 다음과 같다. 두번째 풀이가 훨씬 빠르다는 것을 확인할 수 있다. 

 

아래가 첫번째 풀이, 위가 두번째 풀이