[백준 1964] 오각형,오각형,오각형...

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

문제

오각형의 각 변에 아래 그림과 같이 점을 찍어 나간다. N단계에서 점의 개수는 모두 몇 개일까?

입력

첫째 줄에 N(1≤N≤10,000,000)이 주어진다.

출력

첫째 줄에 N단계에서 점의 개수를 45678로 나눈 나머지를 출력한다.

풀이 

규칙찾기문제입니다. 규칙을 찾아볼까요? 1단계는 5, 2단계는 12, 3단계는 22, 4단계는 35...... 여기서 각 단계는 전 단계 + @이므로 식을 다시 써보면,

1단계->5, 2단계-> 5+7, 3단계->5+7+10, 4단계->5+7+10+13.... 규칙이보이사나요? 맞습니다. 2단계부터 7을 시작으로 3씩 증가하는 등차수열입니다.

식을 그대로 코드로 작성하면됩니다. 주의할건 입력의범위가 크므로 ans를 longlong으로 선언해주는겁니다. 

그리고 dp가 메모리를 많이잡아먹는다는것을 보이기위해 아래에 dp로 푼 실행결과도 올렸습니다.

코드

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	long long ans = 5;
	long long num = 7;
	for (int i = 2; i <= n; i++)
	{
		ans += num;
		num += 3;
		ans = ans % 45678;
	}
	cout << ans << endl;
}

결과

dp

반복문