[알고리즘/Java] 백준 14928번: 큰 수 (BIG)

1. 문제

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

14928번: 큰 수 (BIG)

---

2. 연관 알고리즘

• 수학(Mathematics)
• 사칙연산(Arithmetic)
• 임의 정밀도 / 큰 수 연산(Arbitrary Precision / Big Integers)

---

3. 풀이

3-1. 시간 초과

BigInteger N = new BigInteger(br.readLine());
BigInteger M = new BigInteger("20000303");
bw.append(N.remainder(M) + "\n");

• 지문에서 10의 100만 제곱인 큰 수를 사용한다기에 BigInteger 클래스를 사용했으나, 시간 초과라는 결과가 나왔다.

---

3-2. 정답

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

1 % 13 = 1
2 % 13 = 2
3 % 13 = 3
4 % 13 = 4
5 % 13 = 5
6 % 13 = 6
...
12 % 13 = 12
123 % 13 = 6
64 % 13 = 12
125 % 13 = 8
86 % 13 = 8
...

• 123 % 13 = ((120 % 13) + (3 % 13)) % 13처럼 쓸 수 있는 것이다.
• 구글링 통해 알게 된 '나머지 연산 분배 법칙' 기반 접근 방법 및 풀이과정은 다음과 같다.

String num = br.readLine();
long remainder = 0;
for(int i=0; i < num.length(); i++) {
	remainder = (remainder * 10 + (num.charAt(i) - '0')) % 20000303;
}

• ①큰 수 num을 String 타입으로 입력 받고, for문 통해 num의 자릿수만큼 반복한다.
• ②remainder에 10을 곱한다: remainder *= 10
• ③remainder에 i번째 자릿수를 더한다: remainder += (num.charAt(i) - '0')
• ④문제에서 주어진 대로 remainder의 20000303 나머지를 구한다: remainder %= 20000303

즉, 앞선 공식에서와 같이 num = 123일 때를 가정하거든 반복문을 지나는 동안 아래와 같은 연산이 변수 remainder에 덮어쓰기돼 최종적으로 123이라는 결과값을 리턴한다.
//for문 시작
i = 0 ➡ (0 * 10 + 1) % 20000303 ➡ 결과값 1
i = 1 ➡ (1 * 10 + 2) % 20000303 ➡ 결과값 12
i = 2 ➡ (12 * 10 + 3) % 20000303 ➡ 결과값 123
//for문 끝

---

4. 전체 코드

🌱GitHub(BOJ14928)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String num = br.readLine();
		long remainder = 0;
		for(int i=0; i < num.length(); i++) {
			remainder = (remainder * 10 + (num.charAt(i) - '0')) % 20000303;
		}
		bw.append(remainder + "\n");
		bw.flush();
		bw.close();
		br.close();
	}
}

---

📁References

• https://blex.me/@laetipark/백준bojjava-14928번-큰-수-big
• https://gitseok.tistory.com/entry/백준-14928번-큰-수-JAVA-알고리즘