[백준] no14928: 큰 수(BIG)

문제

주어진 숫자를 20000303으로 나눈 나머지를 출력해야함

문제 링크 : https://www.acmicpc.net/problem/14928

---

원리

1. Biginteger 클래스를 사용 (용량 제한 없이 큰 숫자 사용가능) : 시간초과 발생

* 문제의 취지가 Biginteger 클래스를 사용하지 않고 값을 출력해야 하나봄. 문제 이름에서 낚임

 

2. 나머지 연산 분배 법칙 사용 : 아스키 코드를 이용한 연산 방법

(A + B) % N = ((A % N) + (B % N)) % N

인용 문구

각 피연산자에 모듈러 연산을 취한 후, 계산 결과에 대해 다시한번 모듈러 연산을 취하면 된다.
또한, 뺄셈의 경우 음수가 나오는 것을 방지하기 위해 divisor를 한번 더해준다.

* 만약 나머지가 아닌 나눗셈이 목적이라면 아래의 공식을 적용 (페르마의 소정리를 이용한 변환 공식)

(A / B) % p = (A * B^(p-2)) % p = ((A % p) * (B^(p-2) % p)) % p

---

풀이방법

/**
 * 나머지 연산 분배 법칙 사용
 *
 * 예를 들어,
 * 20000303200003032000030320000303200003032000030320000303200003032000030320000303 일 때,
 * 맨 앞자리 2부터 시작해서 20000303마다 나눠짐.
 * 즉, 20000303으로 나눠지는 수가 되면, 나누고 나머지만 남는 형식
 */

---

나의 코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = br.readLine(); // 입력 값

    long remainder = 0; // 나머지를 저장할 값
    for(int i = 0 ; i<input.length(); i++) {
        remainder = (remainder * 10 + (input.charAt(i) - '0')) % 20000303;
    }
    System.out.println(remainder);
}

---

레퍼런스 코드

아스키코드 링크 : https://stepbystep1.tistory.com/10

참고 링크 : https://blex.me/@Laeti-Park/%EB%B0%B1%EC%A4%80bojjava-14928%EB%B2%88-%ED%81%B0-%EC%88%98-big