2010 정보올림피아드 지역본선 고등부 문제 Review (2)

가로수

  직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.
   편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.
   예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.
  심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.
   실행파일의 이름은 TREE.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
   입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 100,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

출력 형식
   출력 파일의 이름은 OUTPUT.TXT이다. 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

입력과 출력의 예 (1)
입력 (INPUT.TXT)

4
1
3
7
13

출력 (OUTPUT.TXT)

3

입력과 출력의 예 (2)
입력 (INPUT.TXT)

4
2
6
12
18

출력 (OUTPUT.TXT)

5

인접한 가로수들의 간격의 최대공약수를 구해야 하는 문제이다.
가장 기본적인 풀이를 생각하자면, 우선 가로수의 위치를 모두 받고(int position[100000]), 간격을 계산하고(int delta[100000]), 최대공약수를 계산한다. 그리고 간격을 각각 최대공약수로 나눠 더한다.

#include <stdio.h>
int gcd(int a, int b)
{
    int t;
    if (a < b) t = a, a = b, b = t;
    if (a % b == 0)
        return b;
    else
        return gcd(b, a % b);
}
int main()
{
    int i, n;
    int position[100000], delta[100000];
    int g, t = 0;
    FILE *fp;
    fp = fopen("INPUT.TXT", "r");
    fflush(stdout);
    fscanf(fp, "%d", &n);
    for (i = 0; i < n; i++)
    {
        fflush(stdout);
        fscanf(fp, "%d", &position[i]);
    }
    fclose(fp);
    for (i = n - 1; i >= 0; i--)
    {
        delta[i] = position[i + 1] - position[i];
    }
    g = delta[0];
    for (i = 1; i < n - 1; i++)
    {
        g = gcd(delta[i], g);
    }
    for (i = 0; i < n - 1; i++)
    {
        t += delta[i] / g - 1;
    }
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d", t);
    fclose(fp);
    return 0;
}

그러나 메모리와 시간을 아끼자면 몇 가지 대안 풀이를 생각할 수 있다. 일단 간격을 계산하고 나면 위치가 쓸모없어지므로 위치를 받을 때부터 간격을 계산하며, 위치를 저장하지 않는다.

#include <stdio.h>

int gcd(int a, int b)
{
    int t;
    if (a < b) t = a, a = b, b = t;
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
int main()
{
    int a, b = 0;
    int g = 0, t = 0;
    int q[99999];
    int i, n;
    FILE *fp;
    fp = fopen("INPUT.TXT", "r");
    fflush(stdout);
    fscanf(fp, "%d", &n);
    for (i = 0; i < n; i++)
    {
        a = b;
        fflush(stdout);
        fscanf(fp, "%d", &b);
        if (i == 0) continue;
        q[i] = b - a;
        g = gcd(b - a, g);
    }
    for (i = 1; i < n; i++)
        t += q[i] / g - 1;
    fclose(fp);
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d", t);
    fclose(fp);
    return 0;
}

참고로 이 문제에는 가로수의 위치가 오름차순으로 제시된다는 조건이 없다. 따라서 위치를 모두 받고 이를 정렬해 준 후에 간격을 계산하는 것이 맞다. (단, 간격을 위치 배열에 저장해서 메모리를 절약할 수 있다.) 그러나 테스트 데이터는 모두 오름차순으로 제시되어 있었다고 한다. 나는 만약을 생각해 정렬했지만, 문제를 쓰면서 오름차순을 명시하는 걸 빼먹은 모양이다.