[백준/Python] 2193번(DP)_이친수

📌문제 유형

DP(실버3)

 

📌문제

2193번: 이친수

 

📌나의 문제풀이

- 성공

• 첫째칸은 무조건 1, 둘째칸도 규칙에 의해 무조건 0
• 셋째칸 부터 0,1로 나누어 개수 세어보기(0 → 1, 1 → 0,1)
• N = 7까지 늘려보면 앞 2개의 원소를 더한 값이라는 걸 알 수 있음
• dp[i] = dp[i-1] + dp[i-2] 이므로 for문 경계값에 맞춰서 작성

n = int(input())
dp = [0 for _ in range(n+1)]

dp[1] = 1

if n >= 2:
    dp[2] = 1

    for i in range(2, len(dp)-1):
        dp[i+1] = dp[i] + dp[i-1]

print(dp[n])

 

- 실패(메모리 초과)

from itertools import product

n = int(input())
li = list(product([0,1], repeat = n))
ans = 0

for num in li:
    if num[0] == 1 and ('11' not in ''.join(map(str,num))):
        ans += 1
    
print(ans)

 

📌 다른사람의 문제풀이

 

[백준] 2193번(python 파이썬)

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

 

📌 리뷰 

- 일단 나열해보고 규칙찾기