👿 백준 - 9507 Generations of Tribbles

어제 푼 게임이론 DP에 이어서 DP

난 DP가 싫다

DP를 통해 내 뇌 주름의 한계를 가늠해볼 수 있다

쨘 엄마 생일선물용 제작마우스패드 엄마 병원에서 쓰면 좋을 것 같따

젠장....엄마 옆에 있을 때 창 넘기다가 들켜버림..........

올리지말걸...

---

# 9507

Generations of Tribbles

🥈실4

 

 

dp

미리 구했던 dp값이 있으면 다시 계산하지 않도록 해서 시간복잡도를 줄이는 것이 포인트다

def koong(n):
    if n < 2:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return koong(n-1) + koong(n-2) + koong(n-3) + koong(n-4)

이게 아니라

def koong(n):
    if n < 2:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    elif dp[n]:
        return dp[n]
    else:
        dp[n] = koong(n-1) + koong(n-2) + koong(n-3) + koong(n-4)
        return dp[n]

이거!

---

 

3주차 dp......