BAEKJOON #2193 이친수

이 문제의 저작권은 BAEKJOON에 있습니다.

 

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

문제는 위 링크에서 확인할 수 있습니다.

 

#이친수 
#https://www.acmicpc.net/problem/2193
N=int(input())
arr=[1, 2]

for i in range(2,N):
    p = arr[i-1] + arr[i-2]
    arr.append(p)
print(arr[N-2])

문제를 풀기 전 이 문제가 피보나치수열과 연관이 있다는 것을 알아야 합니다.

길이가 1인 이친수 부터 순서대로 이친수의 개수를 보면

1, 1, 2, 3 .... 순으로 피보나치 수열이라는 것을 알 수 있습니다.

 

N이 1일 때	-	-	arr[N-2] = 1
N이 2일 때	-	-	arr[N-2] = 1
N이 3일 때	i = 2	p = 3	arr[N-2] = 2
N이 4일 때	i = 2, 3	p = 3, 5	arr[N-2] = 3

문제 풀이를 표로 정리해보면 위와 같습니다.

for문은 N이 3일때부터 돌아가고 배열의 [i-1] 번째 요소와 [i-2] 번째 요소를 이용해 배열을 추가합니다.

정답은 배열의 -2번째 요소를 가리킵니다.