(백준 알고리즘 문제풀이) 2193번 이친수

문제

문제 링크

 

문제 접근

• dp 문제이자 일반식을 도출해내는 문제인 것 같아서 바로 접근을 시도해보았다.
• An이 피보나치 수열과 동일하다는 일반화를 공식화해내었다.
• An = A(n-2) + A(n-1), n >= 2일 때의 일반식을 도출해냈다.

코드

import sys


def fib(N, memo):
    if N == 1 or N == 2:
        return 1
    elif N not in memo:
        temp = fib(N-2, memo) + fib(N-1, memo)
        memo[N] = temp
        return memo[N]
    else:
        return memo[N]


memo = dict()
N = int(sys.stdin.readline())
print(fib(N, memo))

느낀점

피보나치 수열을 알고있고, 일반식에 대한 개념이 있었기 때문에 알고리즘에 대한 문제를 쉽게 풀었다. 알고리즘은 역시 아는 만큼 푸는 문제인 것 같았다. 더욱 알고리즘에 대한 실력을 키워야겠다고 다짐하게되었다.