[Python] 백준 #2193 - 이친수

문제

---

 

2193번: 이친수

코드

---

My answer

from sys import stdin

n = int(stdin.readline())
dp=[[0,0] for i in range(n+1)]
dp[1]=[0,1]

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

Another answer

a=b=1
for _ in range(int(input())-2):
    a,b= a+b,a
print(a)

 

풀이

---

이전 dp들처럼 우선 i를 자릿수, j를 끝자리로 두고 규칙을 찾아보니까 위처럼 규칙이 나왔다. 맨뒤에 0이 나오면 1을 무조건적으로 붙여도 되는데 1이나오면 0을 붙여야한다. 따라서 위의 점화식과 같은 식이 나온다.내 코드말고 아래 코드는 동일한테 역시나 1차원 배열만 이용해서 문제를 풀었다.

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