규칙성을 찾기
→ dp[0] = 1
→ dp[1] = 2
→ dp[2] = dp[0]+dp[1] = 1+2 = 3
→ dp[3] = dp[1]+dp[2] = 2+3 = 5
→ dp[n-1] = dp[n-3]+dp[n-2] = ?!
dp 사용
→ 2*n 타일링과 유사 ( 이 문제는 효율성 존재 )
def solution(n):
dp = [1,2]
for i in range(2, n):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n - 1] % 1234567
print(solution(1))
( 사용한 메소드, 라이브러리 등 원리 )
dp = []를 생성
규칙성 찾기
→ dp[0] = 1
→ dp[1] = 2
→ dp[2] = dp[0]+dp[1] = 1+2 = 3
→ dp[3] = dp[1]+dp[2] = 2+3 = 5
→ dp[n-1] = dp[n-3]+dp[n-2]
for문을 이용
0,1 부분은 이미 넣어두었기 때문에 range(2,n)으로 범위 지정
각 부분을 대입할수도 있지만 저는 append를 이용
→ dp.append(dp[n-3]+dp[n-2])
n == 1일 경우 예외로 설정
→ 굳이 필요없지만 쓸데없이 돌아가는 코드를 없애기 위함
dp[n-1] 리턴
→ 찾고자하는 n부분의 인덱스는 n-1이기 때문에