백준 9095 파이썬(DP)

일반적인 DP문제다.

 

오랜만에 문제를 풀어서 그런지(코딩 자체가 굉장히 오랜만이다...ㅠㅠ) 문제를 해결하는데 생각보다 오랜 시간이 들었던거 같다.

 

다이나믹 프로그래밍 문제는 

기본적으로 문제를 작게 잘 쪼개는것이 가장 중요하다고 생각한다.

재귀를 이용해서 풀던(탑다운), 반복문을 이용해서 풀던(바텀업) 자기가 생각하기 편한 방식대로 풀면 된다.

 

[DP조건]

1. 중복되는 서브문제(overlapping subproblems) - 문제해결관점
   : 큰 문제를 작은 문제로 쪼갤 수 있고, 큰문제와 작은문제를 같은 방법으로 풀 수 있다. => 메모이제이션
2. 최적 부분 구조(optimal substructure) - 문제의 구조관점
   : 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다.

---

이 문제는 주어진 수의 3번째 전 수의 값을 모두 더하면 답이 나온다.

 

1 -> 1

2 -> 2

3 -> 4

4 -> 7 (1+2+4)

5 -> 13 (7+4+2)

6 -> 28 (13+7+4)

이런식으로...

 

탑다운 방식으로 재귀를 이용해서 풀어보았다.

# 9095번 : 1, 2, 3 더하기

def dp(num):
    if num == 1:
        return 1
    elif num == 2:
        return 2
    elif num == 3:
        return 4
    else:
        return dp(num-1) + dp(num-2) + dp(num-3)

# 문제를 반복하여 풀 횟수
t = int(input())

for _ in range(t):
    i = int(input())
    print(dp(i))