#9095 1,2,3더하기

💯 문제 → 정수 n을 1, 2, 3의 합으로 나타내는 총 경우의 수를 구해야 되는 문제 ! 순서도 생각해 줘야함

<💭 방법>

🎈 1 동적계획법을 사용하는 방법

• 1, 2, 3만을 이용하는 문제여서 일단 먼저 1, 2, 3에 대한 경우의 수를 cache 배열에 저장
• n의 이전의 숫자들을 이용해야함
  ex)
  5 = 1 + 4
  5 = 2 + 3
  5 = 3 + 2 일 경우, 4의 경우의 수를 이용하면 7 + 4 + 2 = 13

<😥 첫번째 코드>

cache = []

cache.append([0, 0])
cache.append([1, 1])
cache.append([2, 2])
cache.append([3, 4])

def Add(n):
    for i in range(4,n+1):
        cache.append([i, cache[i-1][1] + cache[i-2][1] + cache[i-3][1]])
    
    print(cache[n][1])

안된 이유 : cache 배열을 Add 함수 사용할 때 마다 초기화를 해주어야 되는데, 그 부분을 생각하지 못함 ..

<😍 두번째 코드>

def Add(n):
    cache = []

    cache.append([0, 0])
    cache.append([1, 1])
    cache.append([2, 2])
    cache.append([3, 4])

    for i in range(4,n+1):
        cache.append([i, cache[i-1][1] + cache[i-2][1] + cache[i-3][1]])
    
    print(cache[n][1])