[백준 1834] 나머지와 몫이 같은 수

문제출처: https://www.acmicpc.net/problem/1834

문제

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

입력

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

출력

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

풀이

간단해 보이는데 정답률이 낮은문제입니다.제 생각에 수학문제나 dp문제나 메모이제이션의 유무만 다르지 둘 다 규칙찾기문제같습니다.

답이될수 있는 자연수의 범위가 주어지지않았기 때문에 단순히 반복문for(int i=1; i<=200000;i++) 내부에서 1부터 i/n==i%3)인 수를 찾아서 더해가는 풀이는 답이될 수없습니다.  애초에 답이될수 있는 자연수의 범위는 1~200000도 아닙니다. 그럼 규칙을 찾아봅시다.

n=1일때 -> 없음

n=2일때 3

n=3일때 4, 8

n=4일때 5,10,15

n=5일때 6,12,18,24

보이시나요? 여기서 확실하게 알아야될 건 n=4,n=5일때 끝값이 15,24라는 겁니다. 규칙대로 각각 20,30은될 수 없습니다.

n=3일때 나머지로 나올 수잇는 수는 1,2,0으로 3가지인데, 0은 나눠서 나올 수가 없기 때문에 무조건 n-1가지밖에 없습니다.  마찬가지로 n=4일때 나머지는 0,1,2,3이 나올 수 있는데 0은 셈하지않으니 3번연산합니다. 마지막으로 입력값이 최대 20만이라 ans는 int형 범위를 초과할 수 있으므로 longlong 형으로 선언해주면됩니다. 이 것을 코드로 작성하면 끝입니다. 

코드

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	if (n == 0 || n == 1)
	{
		cout << 0 << endl; return 0;
	}
	long long ans = 0;
	for (int i = 2; i <= n; i++)
	{
		ans += (long long)(n + 1) * i;
	}
	cout << ans;
}

결과