[BOJ][B2]오각형, 오각형, 오각형… - 1964

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

문제 전문은 링크 참조

문제가공

1. 단계별로 늘어나는 점의 개수를 세어보면 공차의 수열이 등차수열을 이루는 것을 확인 할 수 있다.

코드작성

아래와 같이 반복문을 돌려주면 테스트에 통과를 하지만, 수가 커질수록 효율이 떨어진다.

• 반복문 (1812ms) 

points = 5
idx = int(input())
gap = 7

for _ in range(1,idx): # 시간복잡도 : O(n)
    points += gap
    gap+=3
print(points%45678)

 

규칙성은 찾았지만, 수식화에 전혀 감이 잡히지 않아서 GPT한테 물어보니 이차수열의 식을 알려줬다.

구해야 하는 항이 세개(A,B,C)이므로, n을 1~3 까지 대입하여 값을 구하자

위의 식을 풀이하면 A = 1.5 , B = 2.5 , C= 1을 구할 수 있다.

• 이차수열 (32ms)
  

  n = int(input())
  answer = 1.5*(n**2) + 2.5*n + 1
  print(int(answer)%45678)
  ​

 

리뷰

아 어려워