[백준, 파이썬] 2193번 이친수

2020. 7. 28. 14:26

2193번: 이친수

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않

www.acmicpc.net

이 문제는 '타일' 문제와 비슷하다

시작은 무조건 1로 시작해야하며, 11이 두 번 연속으로 나타나지 않는 이진수를 찾는 문제이다.

그냥 경우의 수를 나열해 봐도 쉽게 규칙을 찾을 수 있지만

조금만 생각해보면 알고리즘을 금방 생각할 수 있다.

만약 4자리 이친수의 갯수를 찾는다하면 (dp[4]라고 하자)

dp[3](3자리 이친수) 에다 마지막에 '0'을 하나 붙여도 이친수를 만족하며

dp[2](2자리 이친수) 에다 앞에 '10'을 붙여도 위 두 조건을 만족한다

따라서 규칙은 dp[i] = dp[i-1]+dp[i-2]임을 알 수 있다.

코드는 아래와 같다.

n = int(input()) dp = [0, 1, 1] for i in range(3, n+1): dp.append(dp[i-1]+dp[i-2]) print(dp[-1])

printf("hellow coding");