[백준] 이친수

출처:: www.acmicpc.net/problem/2193

분류:: dp

 

1. 문제 이해 및 해결과정

 

1) 자리수별로 풀이

1자리 일때 , 1 2, 10 3, 100 101, 4, 1000 1001 1010 5, 10000,10001,10010,10100,10101 끝자리가 1이면 0만 가능 끝자리가 0이면 , 0과 1 가능   0으로 끝나는 것 1로 끝나는 것 1  0    1 2  1    0 3  1    1 4  1+1  1 5 dp[n][2] dp[i][j]=길이가 i이고 j로 끝나는 것의 개수 dp[i][0]=dp[i-1][0]+dp[i-1][1] dp[i][1]=dp[i-1][0]

 2) 규칙

- dp[i]=dp[i-1]+dp[i-2] 규칙을 찾을 수 있다.

 

2. 풀이방법

  1. [python] dp

#이친수
#https://www.acmicpc.net/problem/2193
import sys
sys.stdin = open("input.txt","r")
n=int(input())
dp=[[0]*2 for _ in range(90+1)]
dp[1][0],dp[1][1]=0,1
dp[2][0],dp[2][1]=1,0

for i in range(3,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. [python] dp

#이친수
#https://www.acmicpc.net/problem/2193
import sys
sys.stdin = open("input.txt","r")
n=int(input())
dp=[0,1,1]

for i in range(3,n+1):
    dp.append(dp[i-1]+dp[i-2])

print(dp[n])

 

3. 오답원인

 

4. 알게된 점