[Python] 백준 2193번 이친수

1. 문제 📚

2. 입출력 예 📋

3. 알고리즘 ✅

• Dp 문제이므로 규칙 또는 점화식을 찾는다

N / 끝의 수	0	1	출력 값(갯수)
1	0	1	1
2	1	0	1
3	1	1	2
4	2	1	3
5	3	2	5
6	5	3	8

규칙을 보면, N이 1과, 2일 땐 1이며 그 이외엔 그 전에 값 2개를 합친 값과 출력 값이 같다는 규칙을 찾을 수 있다.

4. 소스코드 💻

n = int(input())
nums = [1] * n
if n == 1 or n == 2:
    print(1)
else:
    for i in range(2, n):
        nums[i] = nums[i-1] + nums[i-2]

    print(nums[n-1])