1834: 나머지와 몫이 같은 수

https://www.acmicpc.net/problem/1834

1834번: 나머지와 몫이 같은 수

설명

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

핵심 아이디어

처음에는 단순히 조건문을 사용해서 N으로 나눈 몫과 나머지가 같은 수를 찾아 합한 값을 출력하면 되는줄 알았다. 하지만 범위를 지정하는 부분에서 헷갈리고 시간 초과가 발생하는 문제에 직면하였음. 따라서 단순 조건문이 아니라 일정한 패턴을 가진 수학적 접근이 필요함을 발견함.

n = 3
3*1+1 = 4
3*2+2 = 8

n = 5
5*1+1
5*2+2
5*3+3
5*4+4

코드 구현

C++

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	// 입력 최대 값이 2000000이기 때문에
	// int로 표현 불가능 -> long long 사용
	long long n;
	cin >> n;

	long long ans = 0;
	for (int i = 1;  i < n; i++) {
		ans += (n * i + i);
	}

	cout << ans;
}

Python

n = int(input())
# 몫과 나머지가 같은 수를 저장하는 배열
ans = 0
for i in range(1, n):
	ans += n*i+i
print(ans)