C# [백준 BAEKJOON] 2981번 검문

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

 

2981번: 검문

 

 

해당 문제를 해결하기 위해서는 규칙들을 일반화된 공식으로 정의하면 해결이 가능하다.

종이에 적힌 N개의 수들은 모두 나머지를 모두 같게 되는 M을 가지고 있다.

 

A % M = r
B % M = r
C % M = r
D % M = r
......

A% M = B % M이 성립한다는 것을 알 수 있다. (r은 나머지)

이를 A의 약수 형태로 풀어보면
A = M * a + r
B = M * b + r
M을 구하기 위해서 B에서 A를 빼주자.

B - A = M * b + r - M * a - r
B - A = M * b - M * a
B - A = M(b - a)
B- A를 임의의 변수 X로 치환하면
X = M * x

 

B - A = M(b - a) => B- A X로 치환

C - B = M(c - b) => C - B Y로 치환

D - C = M(d - c) => D - C Z로 치환

.....

 

즉, X, Y, Z의 최대공약수인 M을 찾으면 된다는 사실을 알 수 있다. M 구해서 M의 1을 제외한 약수를 출력하자.

 

(B - A)의 모든 약수는 최대 공약 M의 모든 약수이다.

 

함께 읽으면 좋은 글

최대공약수와 유클리드 호제법

 

풀이 코드(시간 초과)

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine();
        var count = Int32.Parse(input);

        List<int> list = new List<int>();

        for (int i = 0; i < count; i++)
        {
            var num = Int32.Parse(Console.ReadLine());

            list.Add(num);
        }

        var max = list.Max();

        for (int i = 2; i <= max; i++)
        {
            var rest = list.First() % i;
            if (list.All(x => rest == (x % i)))
            {
                Console.Write($"{i} ");
            }
        }
    }
}

 

정답 풀이 코드

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine();
        var count = Int32.Parse(input);

        List<int> list = new List<int>();

        for (int i = 0; i < count; i++)
        {
            var num = Int32.Parse(Console.ReadLine());

            list.Add(num);
        }

        list.Sort();

        var newList = new List<int>();
        for (int i = 0; i < list.Count - 1;i++)
        {
            newList.Add(list[i + 1] - list[i]);
        }

        var result = newList.Aggregate(gcd);

        foreach (int i in divisor(result))
        {
            Console.Write($"{i} ");
        }
    }

    static int gcd(int n, int m)
    {
        return (0 < m) ? gcd(m, n % m) : n;
    }

    static IEnumerable<int> divisor(int n)
    {
        for (int i = 2; i <= n; i++)
        {
            if (n % i == 0)
            {
                yield return i;
            }
        }
    }
}

 

참고 사이트

[백준 2981 파이썬] 검문 (골드5, 정수론)

[백준] (2981) 검문