세상을 더 좋게

[백준] 2193 '이친수' 파이썬(python) 본문

Algorithm/DP

[백준] 2193 '이친수' 파이썬(python)

나는SOU 2021. 12. 4. 00:00

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

 

2193번: 이친수

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

www.acmicpc.net

N = int(input())

dp = [0 for _ in range(91)]

for i in range(1, N+1):
    if i == 1:
        dp[i] = 1
    elif i == 2:
        dp[i] = 1
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[N])

Point

  • 점화식을 찾아내서 활용한 DP 문제
  • 점화식이 이전 값들을 사용하기 때문에 DP방식을 사용하면 된다
  • 나열해서 규칙을 찾고 그것을 적용

'Algorithm > DP' 카테고리의 다른 글

[백준] 1912 '연속합' 파이썬(python)  (0) 2021.12.07
[백준] 11053 '가장 긴 증가하는 부분 수열' 파이썬(python)  (0) 2021.12.04
[백준] 14002 '가장 긴 증가하는 부분 수열 4' 파이썬(python)  (0) 2021.12.04
[백준] 10844 '쉬운 계단 수' 파이썬(python)  (0) 2021.12.04
[백준] 16194 '카드 구매하기 2' 파이썬(python)  (0) 2021.11.25
'Algorithm/DP' Related Articles more