https://www.acmicpc.net/problem/2193
2193번: 이친수0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않www.acmicpc.net
dp문제를 풀다보면 해결방안이 보인다.
이친수는 2가지 경우가 있다. 0로끝나는경우, 1으로끝나는 경우
0으로 끝나는 경우에는, 뒤에 0이오던 1이오던 상관없다
1로 끝나는 경우에는, 뒤에 0만 와야한다.
이를 식으로 표현하면
(배열은 각각 2개의원소를 가지고 있는 2차원 배열)
l[i][0]=i번쩨 자릿수가 0으로끝나는경우
l[i][1]=i번째 자릿수가 1로 끝나는 경우
n[i][0]=n[i-1][0]+n[i-1][1]
0으로 끝나는 경우엔 그 전에 0으로끝나든 1로끝나든 상관x
n[i][1]=n[i-1][0]
1로 끝나는 경우엔 그 전이 0으로 끝날 때만 가능
이렇게 배열을 구하고 l[n]을 모두 더하면 (0끝+1끝)
답이나온다.
ㅎ
n=int(input())l=[[0,0] for _ in range(n+2)] #끝0, 끝1l[1]=[0,1]l[2]=[1,0]
for i in range(3,len(l)-1): l[i][0]=sum(l[i-1]) l[i][1]=l[i-1][0]
print(sum(l[n]))