[2193] 이친수

😲 문제

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

이친수는 0으로 시작하지 않는다.
이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력
3

출력
2

❗️ 문제 재정의

1. 0과 1로만 이루어진 수는 이진수이다.
2. 이진수 중 특별한 성질을 갖는 수를 이친수라고 한다.
   1. 이친수는 0으로 시작하지 않는다
   2. 이친수는 1이 두 번 연속으로 나타나지 않는다.
3. n자리 이친수의 개수를 구하여라

딱 봐도 끝나는 숫자가 0인지, 1인지가 중요해보인다.
0으로 끝나면 0이나 1이 올 수 있고
1로 끝난다면 무조건 1이 와야한다.

쉽게 접근하자면 각 자릿수마다 0과 1의 개수를 세면 된다.

0자리
0

1자리 
1 : 1

2자리
10 : 1

3자리
100, 101 : 2

4자리
1000, 1001, 1010 : 3

규칙이 보인다.

✔ 계획 수립

1. 자릿수를 입력으로 받고
2. dp 배열을 우선 0으로 초기화 시킨 후
3. 1 자릿수까지는 초기화 해준다.
4. 나머지 자릿수는 아래 점화식을 이용해서 풀면된다.
   dp[i][0] = dp[i-1][1] + dp[i-1][0]
   dp[i][1] = dp[i-1][0]

👨🏻‍💻 문제 풀이

n = int(input()) # 자릿수 입력

# 딱봐도 끝나는 숫자가 중요해 보인다.
# 0으로 끝나면 0이나 1이 와도 괜찮고
# 1로 끝나면 무조건 0이 와야 한다.
# 쉽게 접근하자면 각 자리수마다 0과 1의 개수를 세면 된다.

dp = [[0] * 2 for _ in range(n+1)] # 0~n 자릿수
dp[1][1] = 1

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

😅 회고

무난하게 쉬운 문제였다.
어떤것이 중요한지만 알고 주어진 규칙을 논리적으로 접근해서 점화식 형태로 작성하면 된다.