문제

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

문제 접근

따라 적어보며 규칙을 파악하려 했다.
1,1,1,2,2,3,4,5,7,9 ....
처음 든 생각

• 모든 부분에서 즉 시작부터 규칙성이 나타나지 않을 수도 있으니 처음엔 적어놓고 시작하자

이 생각과 함께 보니 3부터는 숫자가 한 칸마다 변했다. 그럼 피보나치 수열처럼 이전 것들의 합으로 표현되지 않을까 해서 규칙성을 찾아보니

• f(n+1) = f(n) + f(n-4)

그래서 처음에 n=1 부터 n=100까지 P(n) 값을 리스트에 초기화 해놓고 시작했다.

코드

t = int(input())
tri = [1, 1, 1, 2, 2]
for i in range(4, 100):
    tri.append(tri[i] + tri[i - 4])

for _ in range(t):
    n = int(input())
    print(tri[n - 1])

복잡도 분석

t에 대한 조건은 없다.
n : 1<=n<=100

시간 복잡도

n이 100일 때 for문이 약 100회
tri 리스트에 인덱스로 접근 : O(1)
tri 리스트에 append : O(1)
=> O(n)
그 이후 t에 따라 O(t)

채점 결과 : 68ms

이때

• input() 대신 sys.stdin.readline() 사용
• print 대신 sys.stdout.write()를 사용
• append 대신 tri 리스트를 처음부터 길이 100으로 초기화한 후 인덱스로 접근하여 값 변경
  하면 조금 더 속도를 개선할 수 있을 것 같다.

공간 복잡도

백준에서 파이썬 실행시 기본 약 3만KB는 사용되는 것 같다.
int형 리스트의 길이는 n : O(n)

채점 결과 : 31120KB

학습 포인트

문제의 알고리즘 분류는

• 수학
• 다이나믹 프로그래밍