고관운

1. 2748(피보나치 수 2)

코드

n = int(input())

mlist = [0] * 91
mlist[1] = 1

for i in range(2, n+1):
    mlist[i] = mlist[i-2] + mlist[i-1]
   
print(mlist[n])
Python
복사

피보나치 수

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

초기값 : 0, 1

i≥2 : list[i] = list[i-2] + list[i-1]

풀이 방식

DP로 문제를 접근

n을 입력받고 미리 크기가 n+1인 리스트 생성

인덱스가 1인 곳에 1로 초기화

2부터 n까지 for문을 돌며 인덱스가 i-1, i-2인값을 더한 값으로 초기화

2. 9461(파도반 수열)

코드

mlist = [0] * 101
mlist[1] = 1
mlist[2] = 1
mlist[3] = 1

for i in range(4, 101):
    mlist[i] = mlist[i-2] + mlist[i-3]
  
t = int(input())

for i in range(t):
    n = int(input())
    print(mlist[n])
Python
복사

파도반 수열

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

초기값 : 1, 1, 1

i≥4 : list[i] = list[i-2] + list[i-3]

풀이 방식

2748번과 접근방식 동일

단, 리스트 크기는 주어진 n의 가장 큰 값인 100에 +1한 101로 생성

인덱스가 1, 2, 3인 곳에 1로 초기화

4부터 101까지 for문을 돌며 인덱스가 i-2, i-3인값을 더한 값으로 초기화