[BAEKJOON] 백준 12971: 숫자 놀이 (C#)

문제 링크

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

 

 

문제

준서는 얼마 전 나머지연산에 대해 배웠다. 양의 정수 N을 다른 양의 정수 M으로 나눈 나머지는 항상 0이상 M-1이하의 정수가 된다는 사실이 신기한 준서는 혼자만의 숫자놀이를 고안했다.

먼저 준서는 양의 정수 X1, X2, X3 3개를 임의로 고른다. 그 후 3개의 양의 정수 P1, P2, P3을 고르는데, P1 > X1, P2 > X2, P3 > X3을 만족하도록 고른다. 준서가 알고 싶은 것은 아래의 조건을 만족하는 가장 작은 양의 정수 N이다.

 

N을 P1로 나눈 나머지가 X1, P2로 나눈 나머지가 X2, P3로 나눈 나머지가 X3

 

준서가 선택한 P1, P2, P3, X1, X2, X3가 주어졌을 때, 가장 작은 정수 N을 찾는 프로그램을 작성하시오.

 

 

입력

공백으로 구분된 6개의 정수 P1, P2, P3, X1, X2, X3가 순서대로 주어진다. 모든 숫자는 1과 300사이의 정수다.

 

 

출력

한 줄에 가장 작은 양의 정수 N을 출력한다.

단, 조건을 만족하는 1,000,000,000미만의 양의 정수가 없을 경우 -1을 출력한다.

 

 

 

통과한 답안

namespace _12971
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            int P1 = numbers[0];
            int P2 = numbers[1];
            int P3 = numbers[2];
            int X1 = numbers[3];
            int X2 = numbers[4];
            int X3 = numbers[5];

            int N = X1;
            int step = P1;

            // N % P1 = X1, N % P2 = X2, N % P3 = X3

            while (N < 1000000000)
            {
                if (N % P2 == X2 && N % P3 == X3)
                {
                    Console.WriteLine(N);
                    return;
                }

                N += step;
            }

            Console.WriteLine(-1);
        }
    }
}

 

1이상 1,000,000,000미만인 수 중에서 P1으로 나눈 나머지가 X1,

P2로 나눈 나머지가 X2, P3으로 나눈 나머지가 X3인 숫자를 찾는 문제이다.

 

간단하게 생각해서 아래의 코드와 같이

namespace _12971
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            int P1 = numbers[0];
            int P2 = numbers[1];
            int P3 = numbers[2];
            int X1 = numbers[3];
            int X2 = numbers[4];
            int X3 = numbers[5];

            // N % P1 = X1, N % P2 = X2, N % P3 = X3

            for (int i = 1; i < 1000000000; i++)
            {
                if (i % P1 == X1 && i % P2 == X2 && i % P3 == X3)
                {
                    Console.WriteLine(i);
                    return;
                }
            }

            Console.WriteLine(-1);
        }
    }
}

1부터 1,000,000,000까지의 모든 수들에 대해서 주어진 조건을 만족하는 N을 찾는 방법도 있지만

이는 최악의 경우 시간 복잡도가 O(1,000,000,000)이므로 시간이 오래 걸리는 단점이 있다.

 

따라서 이를 개선한 코드가 정답 코드이며, 시작하는 숫자를 X1으로하고 P1씩 더하는 방식으로

계산하는 숫자들의 수를 획기적으로 줄였으며, if문에서도 조건을 2개로 줄일 수 있었다.

 

이러한 약간의 사고의 전환으로 아래와 같이 시간 복잡도를 약 1/3로 줄일 수 있었다.