n번째 항이 n² − (n−1)²로 주어지는 수열의 첫 N항까지의 합을 구하는 것은 코딩 테스트에서 자주 등장하는 대표적인 수학 문제입니다. 이 수열을 전개해 보면 다음과 같습니다.
n² − (n−1)² = n² − (n² − 2n + 1) = 2n − 1
즉, 이 수열은 1, 3, 5, 7…과 같은 홀수 수열이며, 앞의 항들이 서로 상쇄되는 텔레스코핑(telescoping) 성질에 의해 첫 N항의 합은 간단히 N²이 됩니다.
N이 매우 커질 경우 N² 값이 long 범위를 초과할 수 있으므로, 일반적으로 큰 소수인 1000000007(10⁹ + 7)로 나눈 나머지를 계산합니다. 이는 오버플로를 방지하기 위해 경쟁 프로그래밍에서 널리 사용되는 기법입니다.
예제
public class Demo {
static long my_val = 1000000007;
public static long compute_val(long my_int){
return ((my_int % my_val) * (my_int % my_val)) % my_val;
}
public static void main(String[] args){
long my_int = 45687234;
System.out.println("계산된 값은 ");
System.out.print(compute_val(my_int));
}
}출력
계산된 값은 335959495
코드 설명
Demo라는 이름의 클래스 안에는 compute_val이라는 정적 메서드가 정의되어 있습니다. 이 메서드는 입력값을 미리 정의된 모듈러스 값(1000000007)으로 나눈 나머지를 구한 뒤 제곱하고, 다시 한 번 모듈러 연산을 적용하여 결과를 반환합니다. 입력값을 곱셈 전에 먼저 나누어 주는 이유는 두 수를 곱하는 과정에서 중간 결과가 long 타입의 최대 범위를 넘지 않도록 하기 위함입니다.
main 메서드에서는 long 타입 변수에 원하는 항의 개수(N)를 저장하고, 이 값을 인자로 전달하며 compute_val 함수를 호출합니다. 함수가 반환한 최종 결과가 콘솔에 출력됩니다.
위 예제에서 N = 45687234일 때, 수열의 합은 N² mod 1000000007 = 335959495로 계산됩니다. 이처럼 수학적 성질을 활용하면 반복문 없이 O(1) 시간 복잡도로 답을 구할 수 있다는 점이 이 접근 방식의 가장 큰 장점입니다.