#14928 : 큰 수 (BIG)

풀이방법

사용된 것:

수학

 

2022.05.03

오늘 새벽에 갑자기 올 솔브 배경이 가지고 싶어져서

가장 쉽고 문제 수도 적은 편인 브론즈 5 레벨 문제를 모두 푸는 켠왕을 시작했다.

방금 막 완료했다.

기념샷

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ휴학하니까 별 뻘짓을 다 한다.

브론즈 5 쯤이야 껌이라고 생각했는데 50문제 넘게 풀다 보니 꽤 오래 걸렸다. 그리고 나름 새롭게 알게 된 것들도 있다.

난이도를 버린 대신 유머를 택한 나사 빠진 문제들이 많아서 재미있었다.

 

아무튼 이 글을 쓰는 것은 배경 얻은 날을 기록하기 위해서이기도 하지만

밤새 푼 브론즈 5 문제들 중 적어둘 만 한 문제가 하나 있기 때문이다.

 

14928번 문제는 큰 수의 나머지를 구하는 문제인데, BigInteger를 사용하면 시간초과가 난다.

BigInteger에서 제공하는 mod 연산 함수가 시간이 오래 걸리기 때문이다.

나머지 연산의 수학적 특성을 이용하여 풀어야 한다.

 

바로 다음의 두 가지 특성이다.

 

$\{(A \bmod C) + (B \bmod C)\} \bmod C = (A + B) \bmod C$

$\{(A \bmod C) \times (B \bmod C)\} \bmod C = (A \times B) \bmod C$

 

n을 q로 나눈 몫을 p, 나머지를 r이라 할 때

$n = q \times p + r$

이라는 기본적인 원리를 이용하여 증명할 수 있는 특성이다.

 

수학을 활용하면 효율적인 코드를 짤 수 있다는 것을 기억하자.

정수론과 이산수학 강의에서 들었던 내용들이 은근히 쓸 데가 많다는 것을 느낀다. 강의자료 버리지 말고 잘 가지고 있어야겠다.

 

코드

Java(2022.05.03)

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		String n = sc.next();
		
		int remain = 0;
		for(int i = 0; i<n.length(); i++) {
			remain = (remain*10 + (n.charAt(i)- '0'))%20000303;
		}
		
		System.out.print(remain);
		
		sc.close();
	}
}