백준 1964번: 오각형, 오각형, 오각형…

백준 온라인 저지(BOJ) 1964번 문제

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

1. 문제 요약

주어진 그림대로 오각형을 차례로 그려나갈 때 N번째 그림의 점의 수를 45678로 나눈 나머지 출력

2. 알고리즘

먼저 1개의 공통된 점이 있다.

5각형의 꼭짓점을 이루는 4개의 점은 한 단계마다 4개씩 증가한다.

그 외 3개의 변에 있는 점은 각 단계마다 3(N - 1)개씩 증가한다.

따라서 점화식은 1 + 4 * N + 3 * N * (N - 1) / 2이 된다.

3. 코드

#include <iostream>
using namespace std;

int main() {
	long long N, r;
	cin >> N;

	r = 1 + 4 * N + 3 * N * (N - 1) / 2;
	r %= 45678;

	cout << r << endl;

	return 0;
}