이번 튜토리얼에서는 다음과 같은 문제를 함께 해결해 보겠습니다.
정수 n이 주어졌을 때, (1n + 2n + 3n + 4n) % 5의 값을 구하는 것입니다.
왜 직접 계산할 수 없을까?
n이 조금만 커져도 (1n + 2n + 3n + 4n)의 값은 기하급수적으로 폭발적으로 증가합니다. 실제로 이 값은 long long 자료형의 범위조차 쉽게 초과해 버리기 때문에, 거듭제곱을 직접 계산한 뒤 나머지를 구하는 단순한 방식으로는 해결할 수 없습니다. 따라서 수학적 패턴을 찾아내는 접근이 필요합니다.
패턴 찾기
n = 1부터 9까지 식을 직접 계산하면 각각 10, 30, 100, 354, 1300, 4890, 18700, 72354, 282340이라는 결과를 얻습니다.
이 결과값들을 자세히 관찰해 보면 흥미로운 규칙을 발견할 수 있습니다. 결과값의 마지막 자릿수가 4번마다 반복되는데, 이것이 바로 이 수식의 주기성(periodicity)입니다.
이 주기성을 활용하면 실제로 거듭제곱을 계산하지 않고도 답을 바로 도출할 수 있습니다.
- n % 4 == 0인 경우 → (1n + 2n + 3n + 4n) % 5 = 4
- 그 외의 경우 → 0
예를 들어 n = 4일 때 결과는 354이며 354 % 5 = 4이고, n = 8일 때는 72354이며 마찬가지로 나머지가 4입니다. 반면 n = 1, 2, 3, 5, 6, 7처럼 4로 나누어떨어지지 않는 경우에는 항상 나머지가 0이 됩니다.
C++ 코드 예제
그럼 위 규칙을 적용한 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int findSequenceMod5(int n) {
return (n % 4) ? 0 : 4;
}
int main() {
int n = 343;
cout << findSequenceMod5(n) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
0
n = 343일 때 343 % 4 = 3이므로 4로 나누어떨어지지 않는 경우에 해당하고, 따라서 결과값은 0이 됩니다.
마무리
이처럼 큰 수를 직접 다루지 않고도 수학적 주기성을 이용하면 O(1) 시간 복잡도로 문제를 해결할 수 있습니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.