문제 소개
하나의 자연수 n이 주어졌을 때, 1부터 n까지의 곱(1×2×…×n, 즉 n!)이 1부터 n까지의 합(1+2+…+n)으로 나누어 떨어지는지 판별하는 문제입니다.
예를 들어 num = 5인 경우를 살펴보겠습니다.
- 곱: 1 × 2 × 3 × 4 × 5 = 120
- 합: 1 + 2 + 3 + 4 + 5 = 15
120은 15로 나누어 떨어지므로(120 ÷ 15 = 8) 결과는 True가 됩니다.
접근 방법
곱과 합을 직접 계산한 뒤 나머지 연산을 수행할 수도 있지만, n이 조금만 커져도 곱은 기하급수적으로 증가하기 때문에 비효율적입니다. 대신 수학적 성질을 활용하면 훨씬 간단하게 해결할 수 있습니다.
1부터 n까지의 곱은 n!, 합은 n(n+1)/2로 표현할 수 있습니다. 두 식을 정리하면 다음과 같습니다.
n! ÷ { n(n+1)/2 } = 2 × (n−1)! ÷ (n+1)
결국 이 문제는 (n+1)이 2 × (n−1)!을 나누어 떨어뜨릴 수 있는지를 묻는 것과 같으며, 여기서 다음과 같은 핵심 규칙이 도출됩니다.
- num + 1이 소수(prime)인 경우 → False
n+1보다 작은 수들만으로 이루어진 (n−1)!에는 n+1의 인수가 하나도 포함되어 있지 않으므로 나누어 떨어지지 않습니다. - num + 1이 소수가 아닌 경우 → True
합성수 n+1의 모든 인수는 (n−1)! 안에 이미 포함되어 있으므로 항상 나누어 떨어집니다.
따라서 알고리즘은 다음과 같이 매우 단순해집니다.
- num + 1이 소수인지 검사한다.
- 소수이면 False를, 그렇지 않으면 True를 반환한다.
참고로 n = 1인 경우 곱과 합이 모두 1이므로 항상 나누어 떨어지지만, n+1 = 2가 소수이기 때문에 위 규칙에서는 유일한 예외가 됩니다. 일반적으로 n ≥ 2인 범위에서는 이 규칙이 항상 성립합니다.
구현 예제
아래 코드를 통해 위 내용을 더 잘 이해할 수 있습니다.
def isPrime(num):
if num > 1:
for i in range(2, num):
if num % i == 0:
return False
return True
return False
def solve(num):
if isPrime(num + 1):
return False
return True
num = 5
print(solve(num))
입력
5
출력
True
복잡도 분석
소수 판별 함수는 2부터 num까지 반복하므로 시간 복잡도는 O(N)이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 거대한 곱을 직접 계산하지 않고 소수 여부만 확인하기 때문에 n이 커져도 매우 빠르게 동작합니다.