문제 설명
0->10, 1->01 로 변환하는 규칙을 매 번 모든 인덱스에 적용했을 때, 1로 시작한 n번째 후엔 연속된 0의 그룹이 몇 개 있을지 구해야 한다.
ex) 1 -> 01 -> 1001 -> 01101001 -> 1001011001101001 -> 01101001100101101001011001101001 -> ...
0개, 1개, 1개, 3개, 5개, 11개 ...
풀이 과정
s(i) 를 i 번째 수라고 할 때, i=7까지 직접 써봤다.
그 후 몇 가지 규칙을 찾았다.
1. s(i) = s(i-2)+...+s(1)+'0'+s(i-1)
ex) s(4)='01101001' 는 01, 1, 0, 1001 으로 구성되어있음
2. i홀수 => s(i) 의 양 끝이 1,1
3. i짝수 => s(i) 의 양 끝이 0,1
이 규칙을 이용해 점화식을 세워보았다. dp[i] 를 i 번째 수의 0그룹 개수 라 하면
dp[i] = sum(dp[1] + ... + dp[i-1]) + (1 if i%2==0 else 0)
1 if i%2==0 else 0
: '0'+s(i-1) 에서, 만일 i-1이 짝수면 '0'+'0..' 꼴이므로 0그룹 수가 변하지 않지만, 홀수면 '0'+'1...' 꼴이므로 0그룹수가 하나 늘어난다. i-1홀수 == i짝수
개선
dp[i] = sum(dp[1] + ... + dp[i-1]) + (1 if i%2==0 else 0).
아무리 생각해봐도 반복이 너무 많다. 개선해보자.
짝수 홀수에 따라 값이 변하기 때문에, dp[i+2]-dp[i] 를 계산하면 상수 없이 dp 만 볼 수있다.
dp[i+2]-dp[i] = dp[i+1] + dp[i]
즉, dp[i+1] = dp[i+1] + 2*dp[i] 로 간단하게 쓸 수 있다.
소스코드
n = int(input())
dp = []
dp.append(1) # 0
dp.append(0) # 1
dp.append(1) # 01
for i in range(3, n+1):
re = dp[i-1] + 2*dp[i-2]
dp.append(re)
print(dp[n])