백준 DP - 이친수(파이썬)

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

2193번: 이친수

 

드디어! 혼자 힘으로 풀었습니다😆 DP를 풀다 보니 이제는 요령이란 게 생긴 것 같습니다.

이친수라는 문제는 1과 0으로 이루어진 숫자를 의미하는데 두 가지 조건을 지켜야만 합니다. 첫 번째, 0으로 시작하면 안 된다. 두 번째, 1이 두 번 연속 있으면 안 된다.

그래서 저는 숫자의 일의 자리가 0일 때와 1일 때를 구분해서 값을 넣어주었더니 메모리 초과로 실패했습니다..

n = int(input())
dp = [[1], [0]]

for i in range(2, n+1):
  dp.append([])
  for j in range(0, len(dp[i-1])):
    if dp[i-1][j] == 0:
      dp[i].append(0)
      dp[i].append(1)
    elif dp[i-1][j] == 1:
      dp[i].append(0)

print(len(dp[n-1]))

 

그래서 또 다른 규칙이 있는지 살펴본 결과! 일의 자리가 0이면 0, 1이 올 수 있고, 1이면 0만 온다는 걸 알아채고 전체 수에서 일의 자리가 0인 개수만큼 0과 1이 생기고, 일의 자리가 1인 개수만큼 0이 생긴다는 규칙을 찾아냈습니다.

n = int(input())
sum = 0
dp = [[0, 1], [1, 0]]

for i in range(2, n):
  dp.append([0, 0])
  if dp[i-1][0] > 0:
    dp[i][0] += dp[i-1][0]
    dp[i][1] += dp[i-1][0]
  if dp[i-1][1] > 0:
    dp[i][0] += dp[i-1][1]

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

 

DP 문제는 우선 손으로 그려본 다음에 규칙을 찾아내면 풀 수 있는 것 같습니다.