[Python] 백준 2193번_이친수

문제 

https://www.acmicpc.net/problem/2193

2193번: 이친수

특이점

1. 이친수는 0으로 시작하지 않는다 == 앞자리가 무조건 1로 시작한다.
2. 1이 두번 연속으로 나타나지 않는다 == 이친수가  2자리 이상일 경우, 앞 2자리는 무조건 10으로 시작한다.
3. 반면에 00은 가능하다

→ 10으로 시작하되, 1 다음에는 무조건 0이 나와야 함.

코드

import sys

num = int(sys.stdin.readline())

dp=[[0]*2 for i in range(91)]

for i in range(1,num+1):
    if i == 1 or i == 2:
        dp[i][0] = 1
        dp[i][1] = 0
    elif i == 3:
        dp[i][0]=2
        dp[i][1]=1
    else:
        dp[i][0] = dp[i-1][0]*2 - dp[i-1][1]
        dp[i][1] = dp[i-1][1] + dp[i-2][1]
        
print(dp[num][0])

풀이 

• 자리에 따라 가지치기 하며 전개해본 결과
  • 식 자리수가 n일때, 가능한 경우의 수를 따져보면 전체 경우의 수 * 2 (0, 1) 에서 규칙에 따라 증가하는 수만큼 빼줘야 한다.
  • 0, 1, 1, 2, 3, 5, 8, ... 
• 이차원 배열을 이용해서 풀어보았다.
  
  • 각 차원마다 길이가 2인 배열이 들어간다. DP[n][0] 에는 N자리인 경우 최종 경우의 수가, DP[n][1]에는 N+1의 경우의 수를 구할 때 마이너스 해야하는 수가 들어가 있다.
• 따라서 경우의 수를 구하는 과정은,
  • n-1의 경우의 수의 2배에서 n-2, n-3의 경우에서 뺀 수를 더해 빼준다.
  • 이후 다음 경우의 수를 구하기 위해 빼야 하는 수 (n-1, n-2의 경우에서 뺀 수)를 세팅해준다.

          ⇒ dp[n][0] = dp[n-1][0]*2 - dp[n-1][1] : 자리수가 n인 경우의 수 구해 dp[n][0]에 저장

               dp[n][1] = dp[n-1][1] + dp[n-2][1] : 자리수가 n+1인 경우의 수 구할 때 빼야하는 값 미리 세팅

• 예외 경우))) n = 1, 2, 3 일때  
  • n == 1, 2 의 경우 → 각각 경우의 수가 1가지
  • n == 3 의 경우 → 경우의 수는 2가지, 다음에 빼줘야 하는 수는 1로 미리 세팅

 

다른 풀이 

 출처: https://www.acmicpc.net/source/18672022

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

→ 오 나는 정말 창의롭게 멍청하게 풀기 대회 나가면 일등할듯ㅋㅋ