문제

N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

입력

첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.

출력

첫 줄에 구하고자 하는 수를 출력한다.

문제 자체는 어렵지 않다. 다만, 규칙을 파악했다면 보다 간단히 풀 수 있다.

주어진 문제대로 우직하게 푸는 법.

1부터 n-1까지(8이면 1-7) 각 숫자마다 n을 곱하고 해당 숫자를 더한 값(1*8+1, 2*8+2, …)을 총점에 += 해주면 된다.

n = int(input())
t = 0
for i in range(1, n):
    t += i*n+i
print(t)

규칙을 파악하고 더 쉽게 푸는 법.

n = 1 이면 0
n = 2 이면 3
n = 3 이면 4, 8
n = 4 이면 5, 10, 15
n = 5 이면 6, 12, 18, 24

이를 다시 정리하면 다음과 같다. 이해하기 쉽게 n=5를 기준으로 보자.

result = 1×(n+1) + 2×(n+1) + 3×(n+1) + 4×(n+1) = (1+2+3+4)×(n+1) $={\frac{(4*5)(n+1)}{2}}={\frac{(n-1)n(n+1)}{2}}$

따라서 n으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 코드는 아래와 같다.

n = int(input())
print((n-1)*n*(n+1)//2)

정말 간단하다. :)

[문제 보기]