C++의 정수는 대체로 32비트(int) 혹은 64비트(long long)이고, 이들의 최댓값은 약 2.1 * 10^10, 9*10^18이다. 즉 10^19가 넘는 정수를 입력 혹은 출력하는 문제는 C++에서 지원하는 기본 타입을 이용해서 풀 수 없다.
하지만 피보나치 문제나 조합 문제, 덧셈 문제 등을 보면 입출력 범위가 10^19를 넘어가는 문제를 종종 볼 수 있다. 자바의 경우에는 BigInterger 클래스를 사용해 이러한 수를 다룰 수 있고, 파이썬의 경우에는 int 타입이 자체적으로 저런 정수를 지원하는 반면 C 혹은 C++에선 이러한 큰 정수를 지원하지 않는데, 그렇다면 어떻게 이 문제를 해결해야 할까?
답은 배열을 하나의 타입처럼 사용하는 것이다. 배열의 맨 끝 성분부터 각 성분에 0부터 9까지의 각 digit을 저장한 뒤, 덧셈이 필요할 때는 각 자리를 더하고, 각 자리의 덧셈 결과가 10 이상일 때마다 다음 자리에 현재 자리를 10으로 나눈 값을 더하고 현재 자리에는 10으로 나눈 나머지를 저장하면 두 배열의 덧셈 결과를 얻을 수 있다.
https://www.acmicpc.net/problem/10757
10757번: 큰 수 A+B
두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.
www.acmicpc.net
https://www.acmicpc.net/problem/4150
4150번: 피보나치 수
피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력
www.acmicpc.net