백준 1206번 - 사람의 수(C++)

문제

• 백준, 골드 5, https://www.acmicpc.net/problem/1206
• 알고리즘 분류: 
• 사용 언어: C++

문제 해설

해당 문제는 처음에 떠올린 해결 방법이 잘못된 경우였다. 그 때문에 고생하기도 했고, 예상했던 부동소수점의 오차 문제에 대해서도 많이 고민하게 한 문제라고 할 수 있다. 하나의 접근 방법을 떠올리고 나서 이를 검증하는 과정이 중요하다는 것을 알 수 있었다.

초기 시도: 최소 공배수로 접근하자(실패)

처음에는 각 문항별로 필요한 최소 사람의 숫자를 구한 후, 이들 사이에 최소 공배수를 구하는 식으로 접근하였다.

계산 시 floating point로 접근하면 정확하게 숫자가 구해지지 않으므로 Fixed Point 자료구조를 직접 구현하도록 했다.

그러나 최소 공배수로 구하면 정확히 값이 구해지지 않는다.

최초 접근식에는 다음과 같이 생각했다.

$$average={sum \over n}$$

평균값은 위와 같이 기술되므로 합 sum은 average를 통해 구할 수 있다.

$$n*average=sum$$

그런데 문제는 평균 점수는 소수점 셋째 자리에서 잘린 값이라는 점이다.

그로 인해, 정확히 average에 n을 곱해도 sum이 정수에 약간 못 미치는 경우가 존재했다.

따라서 다음과 같이 문제를 정의했다.

$$naverage \le sum < n(average+0.001)\text{인 양의 정수 sum이 존재할 때, }\\ \text{모든 average에 대해 n의 최소 공배수를 구하기.}$$

average에 대해 n명마다 딱 나누어 떨어지는 정수 값이 존재한다고 생각했다.

하지만 그렇지 않았다.

참고: https://www.acmicpc.net/board/view/68319

위 링크에는 다음과 같은 반례가 주어져 있다.

input 
3
4.864
5.027
5.000

answer 
37

최소 공배수 방식에 따라 구하면, 첫 번째 수 4.864는 37명마다, 두 번째 수 5.027은 36명마다, 세 번째 수는 이미 정수이므로 1명마다 average가 정수가 된다고 생각할 수 있다.

하지만, 5.027은 36일 때에도 정수가 되지만 37일 때에도 정수가 된다.

5.027 * 36 = 180.972 < 181 < 5.028 * 36 = 181.008

즉, 규칙성을 찾기 어려우므로 최소공배수로는 문제를 해결할 수 없고, 브루트포스를 사용하는 수밖에 없다.

이분 탐색으로 구현하기

따라서 인원 수가 K명일 때 모든 평균 점수를 만들 수 있는지로 검사한다.

이때 모든 사람은 각각 점수를 0점에서 10점까지 정수 단위로만 줄 수 있으므로 5명일 때 가능한 평균 점수는 1/5, 2/5, 3/5, …, 49/5, 50/5점까지 존재한다. 목표 점수가 0.600이라면, 3/5가 정답이 된다. 이렇게 모두 조사해서 딱 값이 떨어지는 인원수를 찾아야 한다.

이때 특징은 1000명이 존재하면 어떤 점수든지 만들 수 있다는 점이다. 소수점 세 자리까지 표시되므로, 1000을 곱하면 무슨 수든 정수로 만들 수 있다.

즉, 1명부터 1000명까지 모든 인원수에 대해 딱 점수가 떨어지는 경우의 수가 존재하는지 검사해야 한다.

이때 K명일 때 목표 점수에 가장 가까운 점수(혹은 같은 점수)를 찾아야 하는데, 모두 찾는 것보다는 이분 탐색으로 탐색하는 것이 훨씬 유리하다. 따라서 이분 탐색을 사용하면 좀 더 최적화할 수 있다.

탐색시 부동소수점 오차 문제가 있으므로, 점수에서 1000을 곱한 후 인원수 K로 나누도록 한다.

단, 입력받을 때 주의해야 하는 점은 0.300 같은 값을 입력받을 때 정수로 받아야 한다는 것이다. 0.300을 double로 받으면 0.299로 계산되어 정답이 달라질 수 있다는 점이다.

따라서 문자열을 입력받고 ‘정수.정수’의 형태로 파싱해야 한다.

#include <iostream>
#include <string>

using namespace std;

bool FindExactlyEqualNumber(int divisor, int target)
{
    int left = 0, right = divisor * 10, mid;
    int fraction;

    while (left <= right)
    {
        mid = (left + right) / 2;
        fraction = mid * 1000 / divisor; // 총점 / 인원수를 정수(*1000)로 구하기

        if (fraction > target)
        {
            right = mid - 1;
        }
        else if (fraction < target)
        {
            left = mid + 1;
        }
        else // ==
        {
            return true;
        }
    }
    return false;
}

int main()
{
    int n;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int averageInt[50];
    int integer, fraction;
    string input;

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> input;
        int idx = input.find('.');
        integer = stoi(input.substr(0, idx));
        fraction = stoi(input.substr(idx+1));
        averageInt[i] = integer * 1000 + fraction;
    }

    bool success;
    for (int i = 1; i <= 1000; i++)
    {
        success = true;
        for (int j = 0; j < n; j++)
        {
            if (!FindExactlyEqualNumber(i, averageInt[j]))
            {
                success = false;
                break;
            }
        }
        if (success)
        {
            cout << i << "\\n";
            break;
        }
    }

    return 0;
}