[백준/C# (.NET) 14928번 큰 수 (BIG)]

 

백준 온라인 저지 / 14928 큰 수 (BIG)

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

14928번: 큰 수 (BIG)

 

• 사용언어 : C# (.NET)
• 알고리즘 : 수학, 임의 정밀도, 큰 수 연산

 

 

C#코드

1. 문제 정리

 

이번 문제는 저번에 풀었던 문제 같이 BigInteger을 쓰면 틀린다. 

 

왜? 라고 묻는다면 시간초과라고 대답 해주지.

 

 

이 문제 덕분에 정답 비율이 낮아졌다 ^^

 

BigInteger str = BigInteger.Parse(Console.ReadLine());
BigInteger i1 = str % 20000303;
Console.WriteLine(i1);

처음 접근 방식은 이렇게 했지만, BigInt의 미친 메모리 잡아먹기 덕분에 시간 초과로 탈락! 선언을 받았다.

 

그럼 어떤 방식으로 접근 할 수 있을까?

 

 

2. 모든 숫자를 나눠서 계산해보자

 

숫자를 뭉탱이로 받지 말고 for문을 통해 1자리씩 나눠보는 방식을 사용하기로 하였다.

 

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

for문으로 i<str의 길이 까지 돌린다고 되어 있으니 

만약 20자리라면 1~20자리 수 까지 나눠지는 구조를 가지는 것이다.

 

예제처럼 20000303200003032000030320000303200003032000030320000303200003032000030320000303을 입력 받는다면,

첫자리 2000~~ 을 20000303으로 나누고 남은 나머지에 10을 곱하고 다시 value값에 저장 그리고 그 다음자리를 또 20000303으로 나누고 남은 나머지에 10을 곱하고 다시 value값에 저장하여서 그냥 작은수로 나눠질 수 있게 만든 구문이다. 

---

3. 코드 작성

 

using System;

namespace boj
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = Console.ReadLine();
            int value = 0;

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

            Console.WriteLine(value);   
        }
    }
}