[알고리즘][백준] 2193번 이친수 - 파이썬(python) 풀이

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

2193번: 이친수

---

이번에도 0, 1로 끝나는 수의 개수를 dp에 넣어 2차원 형태로 진행하였다

0 -> 0, 1
1 -> 0

import sys

n = int(sys.stdin.readline())

# 0, 1로 끝나는 수의 개수
dp = [[0,0] for _ in range(91)]
dp[1] = [0, 1]
dp[2] = [1, 0]
dp[3] = [1, 1]

for i in range(4, n+1):
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    dp[i][1] = dp[i-1][0]

print(sum(dp[n]))

 

 

다른분들 풀이를 살펴보니 2차원으로 푼 사람은 별로 없다..?!

위와 같은 점화식이 나올수있다

# # sol2

import sys

n = int(sys.stdin.readline())

dp = [0] * 91

dp[1] = 1

dp[2] = 1

for i in range(3, n+1):

    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

시간도 더 빠르다!!

 

2193_이친수.py

0.00MB