[Bronze5][14928]큰 수 (BIG)

14928번: 큰 수 (BIG) (acmicpc.net)

14928번: 큰 수 (BIG)

 

1271번에서 사용한 BigInterger를 사용하면 시간초과가 발생한다. 따라서 나머지 연산자의 특징을 사용해서 더 최적화된 알고리즘으로 문제를 풀어야 한다.

 

우선 초등학교 때 배운 나눗셈으로부터 나머지를 어떻게 우리가 구했는지 예를 통해 살펴보자.

 

예) 236을 7로 나누는 경우

 

1. 우선 2를 7로 나누어 본다. 2는 7보다 작은 숫자이므로 다음자리인 3으로 넘어간다.

그러면 23이 되고 23 나누기 7의 나머지는 2가 되고 아래에 적는다.

여기서 2에서 23으로 넘어가는 과정은 2에 10을 곱하고 다음 자리인 3을 더해준 과정이다. 

따라서 위 과정을 식으로 나타내면 아래와 같다.

(2 * 10 + 3) % 7 = 2

 

2. 다음 자리수인 6을 내린다.

1번에서의 원리와 마찬가지로 6을 내린다는 것도 사실 직전에 구한 나머지 2에 10을 곱하고 6을 더한것과 같다.

따라서 이것도 식으로 나타내면 다음과 같다.

(2 * 10 * 6) % 7 = 5

 

236 나누기 7을 전체 식으로 나타내면 다음과 같다.

(((2 * 10 + 3) % 7) * 10 + 6) % 7 = 5

 

제일 처음 (2 * 10 + 3) % 7 부분을 전체 식의 규칙에 맞게 일반화하면 다음과 같이 나타낼 수 있다.

((((0 * 10 + 2 % 7) * 10 + 3) % 7) * 10 + 6) % 7 = 5

 

반복문으로 돌리기 위해서는 아래 규칙을 통해 구할 수 있을 것이다.

sum = 0부터 시작(위 식의 파랑색 0)

 

i) sum = 0

(sum * 10 + 2) % 7 = 2, 이 값을 새로운 sum으로 대입

 

ii) sum = 2

(sum * 10 + 3) % 7 = 2, 이 값을 새로운 sum으로 대입

 

iii) sum = 2

(sum * 10 + 6) % 7 = 5, 이 값을 새로운 sum으로 대입

 

최종 sum = 5가 되고, 따라서 236 % 7  = 5가 되는 것이다.

따라서 위 사실을 이용하여 아래와 같이 코드를 작성할 수 있다.

 

 

코드

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string number = Console.ReadLine();

            int sum = 0;
            for(int i = 0; i < number.Length; i++)
            {
                int digit = number[i] - '0';
                sum = (sum * 10 + digit) % 20000303;
            }

            Console.WriteLine(sum);
        }
    }
}