[Python] 백준 1964번: 오각형, 오각형, 오각형…

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

 

 

 

 

[풀이]

처음에는 이렇게 나누어 풀었었다.

좌측 하단의 꼭짓점을 기준으로, 

 

중앙의 점 1개

그 외 꼭짓점으로부터 뻗어나가는 부분 4개에 대해 (n-1)개

그리고 나머지 3개 부분에 대한 (n-1)!개의 꼭짓점을 합해서

1 + 4n + 3 * (n - 1)! 개라고 식을 도출했었다.

 

하지만, 이렇게 하면 factorial을 사용해야 했기 때문에, 더 좋은 방식을 찾고자 했다.

등차수열을 이용하는 것이다.

 

우선, 전체에 대해 각각의 오각형을 중복을 생각하지 않고 개수를 구한다면

5 + 10 + 15 + 20 + ... 5  * n 개의 꼭짓점이 나올 것이고

이것을 공식화 한다면 5 * (n * (n - 1)) / 2 라는 공식이 나온다.

1, 2, 3, 4... 에 대한 공식이 n * (n - 1) / 2 인데, 거기에 5를 곱했기 때문.

 

여기서 중복을 빼기 위한 공식은

0, 3, 8, 15, 24 ... 인데

이린 수열은 1, 4, 9, 25 ... 와 유사한 형태를 보인다.

이를 통해 n^2 - 1 이라는 공식을 도출할 수 있다.

 

따라서, 5 * (n * (n - 1)) / 2 을 구하고, n^2 - 1을 뺀다면, n에 대한 꼭짓점 개수를 구할 수 있다.

이를 구하면

5 * (n * (n - 1)) / 2 - (n^2 - 1)

= (3n^2 + 5n + 2) / 2

 

라는 공식을 도출할 수 있다.

 

 

하지만, n의 최댓값이 10,000,000 이므로

이를 result로 출력하기 위해서는 45,678로 나누어 주어야 한다.

 

 

이는 (3n^2 + 5n + 2) / 2 라는 공식을

(n(3n + 5) + 2) / 2 라는 공식으로 변형시켜서, 곱셈부가 나오는 부분에

45,678로 연산 때마다 나누어주어 값이 너무 커지지 않게 해줄 수 있다.

 

 

 

 

[코드]

n = int(input())
result = (3 * n ** 2 + 5 * n + 2) // 2 % 45678
print(result)

 

 

 

 

[시간복잡도]

O(1)