Jungol] 2499: 저울 (2011년 KOI 초등부)

2011년 한국정보올림피아드(KOI) 초등부 문제 : 저울

이 문제의 답안과 채점은 Jungol이라는 사이트에서 이뤄졌다.

(문제 번호 2499 : 저울)

필자는 두 가지 답안을 작성했다.

그리디 알고리즘을 통해 최적해를 구하는 방법을 잘못 접근했기 때문인데,

최대에서 최소로 최적해를 구성하면서 TLE(시간 초과) 문제가 발생해서 만점을 받지 못했고,

최소에서 최대로 최적해를 구성하는 건, TLE 문제를 해결할 수 있었다.

아주 간단한 원리를 까먹고 진행해서... 

1안 : TLE 발생

#include <iostream>
using namespace std;
int main(void)
{
    int n;
    int arr[1000];
    int mass1 = 1, mass2;
    int i, j, tmp;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    /* 합을 구성하되 최대에서 최소 순서로 탐색하며 조합하면서 구성 가능성 따지기 */
    /* TLE(Time Limit Error) 발생 */
    if (arr[n - 1] != 1)
    {
        cout << "1";
        return 0;
    }
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (arr[i] < arr[j])
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    while (1)
    {
        mass2 = mass1;
        i = 0;
        while (i < n && mass2 != 0)
        {
            if (mass2 >= arr[i])
            {
                mass2 -= arr[i];
            }
            i++;
        }
        if (mass2 > 0)
            break;
        mass1++;
    }
    cout << mass1;
    return 0;
}

2안 : TLE 통과

#include <iostream>
using namespace std;
int main(void)
{
    int n;
    int arr[1000];
    int i, j, tmp;
    int sum;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    /* 최소에서 최대로 구성, 합을 구성하는 방식으로 */
    /* 추의 무게합이 다음 무게보다 적었을 때 탐색 */
    /* 다음 추의 무게가 이 무게를 측정하지 못하면 측정 불가 */
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (arr[i] > arr[j])
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    if (arr[0] != 1)
    {
        cout << "1";
        return 0;
    }
    sum = arr[0];
    for (i = 1; i < n; i++)
    {
        if (sum + 1 >= arr[i])
        {
            sum += arr[i];
        }
        else
        {
            break;
        }
    }
    cout << sum + 1;
    return 0;
}