문제
N번째 오각형에 포함된 점의 개수를 45678로 나눈 나머지를 출력하라. 각 단계에서 이전 오각형에 점을 추가하여 다음 오각형을 만든다.
입력
자연수 N이 주어진다.
출력
N번째 오각형의 점 개수를 45678로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 | 5 |
풀이
오각형 수의 점 개수에 대한 수학 공식을 유도하여 O(1)에 계산한다.
- N = 1이면 5를 출력한다
- N번째 오각형 수 =
((2 + N + 1) / 2) * N * 3 - 2N + 1로 등차수열의 합을 이용한다 - 결과를 45678로 나눈 나머지를 출력한다
핵심 아이디어: 매 단계에서 추가되는 점의 수가 등차수열을 이루므로, 등차수열의 합 공식으로 N번째 오각형 수를 O(1)에 직접 계산할 수 있다.
코드
#include <iostream>
int main(void)
{
int N;
std::cin >> N;
if (N == 1)
std::cout << 5;
else
std::cout << ((long)(((2 + N + 1) / (double)2) * N * 3 - 2 * N) + 1) % 45678;
return 0;
}복잡도
- 시간: O(1)
- 공간: O(1)